用DFS求连通块问题

2019-04-15 15:10发布

站内文章 / PIC单片机
12229 0 1268
这是题目： 先给出输入输出示例图：   代码和注释都比较详细了，如下给出： #include #include using namespace std; const int maxn = 100; char pic[maxn][maxn];//pic用于表示邻接矩阵 int m, n, 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 || pic[r][c] != '@')return;//不是@的格子或者访问过的格子 idx[r][c] = id;//id是连通分量编号 //验证格子的四周是否连通 for (int dr = -1; dr <= 1; dr++)//遍历行 for (int dc = -1; dc <= 1; dc++)//遍历列 if (dr != 0 || dc != 0)dfs(r + dr, c + dc, id); } int main() { while (cin >> m >> n)//m行n列 { for (int i = 0; i < n; i++) cin >> pic[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 && pic[i][j] == '@') dfs(i, j, ++cnt); cout << cnt << endl; } system("pause"); return 0; }  

热门文章