DFS求连通块数目(深搜)

DFS求连通块数目

这里认为，连通块是包括斜对角线的路径连通的块。

测试数据

5 5 ****@ *@@*@ *@**@ @@@*@ @@**@

计算通过@相连的连通块的个数

测试输出：

2

---

样例代码

#include <iostream> using namespace std; #include <cstring> const int MAX = 100 + 5; char G[MAX][MAX]; bool visited[MAX][MAX]; int m, n, id; void DFS(int x, int y) {if (visited[x][y]) return;visited[x][y] = true;for (int i = -1; i <= 1; ++i) {for (int j = -1; j <= 1; ++j) {if (x + i >= 0 && x + i < m && y + j >= 0 && y + j < n && !visited[x+i][y+j] && G[x+i][y+j] == '@') {DFS(x + i, y + j);}}} } int main() {while (cin >> m >> n) {id = 0;for (int i = 0; i < m; ++i) cin >> G[i];memset(visited, false, sizeof(visited));for (int i = 0; i < m; ++i)for (int j = 0; j < n; ++j)if (!visited[i][j] && G[i][j] == '@'){id++;DFS(i, j);}cout << id << endl;} }

总结

以上是生活随笔为你收集整理的DFS求连通块数目(深搜)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。