POJ 2386 Lake Counting：DFS 連通分量計數

POJ 2386 Lake Counting 題目詳解

給定 N×M 網格，'W' 表示水，'.' 表示陸地。水池定義為 8 方向連通的 'W' 區域。求水池個數。N,M ≤ 100。

DFS 洪水填充

遍歷所有格子，遇到 'W' 即發起 DFS，將連通的 'W' 全部標記為 '.'，計數器 +1。8 方向偏移：(-1,-1) 到 (1,1) 除 (0,0)。每個格子最多進棧一次，時間 O(NM)。

代碼實現

#include 
#include 
using namespace std;

char grid[105][105];
int N, M;
int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};

void dfs(int x, int y) {
    grid[x][y] = '.';
    for (int d = 0; d < 8; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
        if (grid[nx][ny] == 'W') dfs(nx, ny);
    }
}

int main() {
    while (cin >> N >> M) {
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                cin >> grid[i][j];
        int ans = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                if (grid[i][j] == 'W') {
                    dfs(i, j);
                    ++ans;
                }
        cout << ans << endl;
    }
    return 0;
}

遞歸深度與棧溢出

N,M ≤ 100，最大遞歸深度 10000，默認棧通常足夠。若擴大到 1000×1000，需改用顯式棧 BFS 或增大棧大小。

變形：統計每個水池大小

在 dfs 中引用計數器累加，返回大小，存入 vector 後可求最大/最小/平均水池面積。