首页 > 代码库 > DFS入门之二---DFS求连通块
DFS入门之二---DFS求连通块
用DFS求连通块也是比较典型的问题， 求多维数组连通块的过程也称为--“种子填充”。
我们给每次遍历过的连通块加上编号， 这样就可以避免一个格子访问多次。比较典型的问题是”八连块问题“。即任意两格子所在位置相邻（上下左右对角共八个方位），则在一个连通块。典型例题：HDU 1241 Oil Deposits
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1241
题目描述：输入m行n列的字符矩阵， 统计字符“@”组成八连块的个数。
题意分析：读入数据 -> 通过二重循环遍历该图->遇到‘@’且没有被访问过->DFS其连通块并作标记->输出
代码（仅供参考）：
#include <cstdio>#include <cstring>const int maxn = 100 + 10;char a[maxn][maxn];int n, m, idx[maxn][maxn];void dfs(int r, int c, int id){ if(r < 0 || r >= m || c < 0 || c >= n) return ; if(idx[r][c] > 0 || a[r][c] != ‘@‘) return ; idx[r][c] = id; for(int i = -1; i <= 1; i++) for(int j = -1; j <= 1; j++) if(i != 0 || j != 0) dfs(r+i, c+j, id);}int main(){ while(~scanf("%d%d", &m, &n)){ if(n == 0 && m == 0) break; for(int i = 0; i < m; i++) scanf("%s", a[i]); memset(idx, 0, sizeof(idx)); int cnt = 0; for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) if(idx[i][j] == 0 && a[i][j] == ‘@‘) dfs(i, j, ++cnt); printf("%d\n", cnt); } return 0;}
DFS入门之二---DFS求连通块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。