POJ 2386 Lake Counting DFS 連通分量計數

POJ 2386 Lake Counting 題目解析

N×M 網格 (≤100×100)，'W' 表示水，'.' 表示陸地。八方向連通的 'W' 形成一個湖。計算湖的數量。經典 DFS 洪水填充算法。

DFS 遞歸實現

#include <iostream>
#include <cstdio>
using namespace std;

const int MAX_N = 101, MAX_M = 101;
int n, m;
char field[MAX_N][MAX_M];

void dfs(int x, int y) {
    field[x][y] = '.';
    for (int dx = -1; dx <= 1; dx++)
        for (int dy = -1; dy <= 1; dy++) {
            int nx = x + dx, ny = y + dy;
            if (0 <= nx && nx < n && 0 <= ny && ny < m && field[nx][ny] == 'W')
                dfs(nx, ny);
        }
}

void solve() {
    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (field[i][j] == 'W') {
                dfs(i, j);
                res++;
            }
    printf("%d\n", res);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> field[i][j];
    solve();
    return 0;
}

關鍵點

• 八方向：dx, dy ∈ {-1,0,1} 且不全為 0
• 就地修改標記訪問：'W' → '.'，無需額外 visited 數組
• 遞歸深度 ≤ 10000，棧空間通常足夠
• 輸入讀取：cin 直接讀 char，自動跳過換行

編譯錯誤避坑指南

• POJ 需選擇正確編譯器 (GNU C++ / C++11)
• main 返回 int，包含必要頭文件
• 數組大小 MAX_N+1 防止越界
• 括號匹配：while 迴圈結構正確

複雜度

• 時間：O(N×M)，每格最多訪問一次
• 空間：O(N×M) 網格 + O(N×M) 遞歸棧 (最壞全 W)