用dfs求联通块(UVa572)
DFS 联通
2023-09-27 14:27:46 时间
一、题目
输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块。如果两个字符所在的格子相邻(横、竖、或者对角线方向),就说它们属于同一个八连块。
二、解题思路
和前面的二叉树遍历类似,图也有DFS和BFS遍历。由于DFS更容易编写,一般用DFS找联通块:从每个“@”格子出发,递归遍历与之相邻的“@”格子,标记相同的“联通分量标号”。这样在访问之前需检查它是否已经有了编号,从而避免一个格子访问多次。
三、代码实现
1 #include<stdio.h> 2 #include<iostream> 3 using namespace std; 4 5 const int maxn = 100 + 10; 6 char field[maxn][maxn]; 7 int N, M; 8 9 void dfs(int x, int y) 10 { 11 field[x][y] = '*'; //这里通过把“@”换成“*”,从而避免重复 12 for (int dx = -1; dx <= 1; dx++) 13 for (int dy = -1; dy <= 1; dy++) 14 { 15 int nx = x + dx; int ny = y + dy; 16 if (nx >= 0 && nx < N && ny >= 0 && ny < M && field[nx][ny] == '@') 17 dfs(nx, ny); 18 } 19 return; 20 } 21 void slove() 22 { 23 int res = 0; 24 for (int i = 0; i < N; i++) 25 for (int j = 0; j < M; j++) 26 { 27 if (field[i][j] == '@') 28 { 29 dfs(i, j); 30 res++; //遍历完一个连通分量,答案加一 31 } 32 } 33 printf("%d\n", res); 34 } 35 int main() 36 { 37 while (scanf("%d%d", &N, &M) == 2 && N) 38 { 39 for (int i = 0; i < N; i++) 40 for (int j = 0; j < M; j++) 41 cin >> field[i][j]; 42 43 slove(); 44 } 45 return 0; 46 }
相关文章
- hdu4848 DFS 暴搜+ 强剪枝
- hdu4665 DFS
- nyist oj 19 擅长排列的小明(dfs搜索+STL)
- MFC dfs遍历文件
- 【BZOJ2783】[JLOI2012]树 DFS+栈+队列
- zoj 1008 DFS
- 【创】C/C++无向图-邻接矩阵表示法 & DFS & BFS & 连通图 & 回路
- HDU 2102 A计划 (BFS或DFS)
- 【cf842C】 Ilya And The Tree(dfs、枚举因子)
- BFS(广搜)DFS(深搜)算法解析
- 48、【图】排列数字——DFS(C/C++版)
- [dfs] UVALive 3667 Ruler
- POJ-1190-生日蛋糕-DFS(深搜)-枚举-多重剪枝
- 信号与系统——FT、FS、DTFT、DFS、DFT、FFT(一)
- nyoj 27-水池数目(BFS, DFS)
- H - Graphics(dfs)