DFS入门之二---DFS求连通块

时间：2024-04-06 19:36:48

用DFS求连通块也是比较典型的问题， 求多维数组连通块的过程也称为--“种子填充”。

我们给每次遍历过的连通块加上编号， 这样就可以避免一个格子访问多次。比较典型的问题是”八连块问题“。即任意两格子所在位置相邻（上下左右对角共八个方位），则在一个连通块。典型例题：HDU 1241 Oil Deposits

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1241

题目描述：输入m行n列的字符矩阵， 统计字符“@”组成八连块的个数。

题意分析：读入数据 -> 通过二重循环遍历该图->遇到‘@’且没有被访问过->DFS其连通块并作标记->输出

代码（仅供参考）：

#include <cstdio>

#include <cstring>

const int maxn =  + ;

char a[maxn][maxn];

int n, m, idx[maxn][maxn];

void dfs(int r, int c, int id)

{

    if(r <  || r >= m || c <  || c >= n) return ;

    if(idx[r][c] >  || a[r][c] != '@') return ;

    idx[r][c] = id;

    for(int i = -; i <= ; i++)

        for(int j = -; j <= ; j++)

            if(i !=  || j != ) dfs(r+i, c+j, id);

}

int main()

{

    while(~scanf("%d%d", &m, &n)){

        if(n ==  && m == ) break;

        for(int i = ; i < m; i++) scanf("%s", a[i]);

        memset(idx, , sizeof(idx));

        int cnt = ;

        for(int i = ; i < m; i++)

            for(int j = ; j < n; j++)

                if(idx[i][j] ==  && a[i][j] == '@') dfs(i, j, ++cnt);

        printf("%d\n", cnt);

    }

    return ;

}

相关文章