DFS求連通塊數(shù)目

這里認(rèn)為，連通塊是包括斜對角線的路徑連通的塊。

測試數(shù)據(jù)

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

計算通過@相連的連通塊的個數(shù)

測試輸出：

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;} }

總結(jié)

以上是生活随笔為你收集整理的DFS求连通块数目(深搜)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。