UVA 572 Oil Deposits：DFS 求八連通分量計數油田

問題描述

給定 N x M（≤ 100）網格，'W' 代表水，'.' 代表陸地。八方向相連的 'W' 組成一個池塘。求池塘總數。

解法：DFS 洪水填充

• 遍歷每個格子，若為 'W' 且未訪問，發起 DFS，標記所有八連通 'W' 為同一池塘（賦予唯一 ID），計數器加 1。
• DFS 遞歸訪問 8 個鄰居（dr = -1..1, dc = -1..1，排除 (0,0)）。
• 邊界檢查：r < 0 || r >= m || c < 0 || c >= n 返回。

完整代碼

#include 
#include 
const int maxn = 1000 + 5;
char grid[maxn][maxn];
int idx[maxn][maxn]; // 0=未訪問, >0=池塘ID
int m, n;

void dfs(int r, int c, int id) {
    if (r < 0 || r >= m || c < 0 || c >= n) return;
    if (idx[r][c] > 0 || grid[r][c] != 'W') return;
    idx[r][c] = 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 (scanf("%d%d", &m, &n) == 2 && m && n) {
        for (int i = 0; i < m; i++) scanf("%s", grid[i]);
        memset(idx, 0, sizeof(idx));
        int ponds = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (idx[i][j] == 0 && grid[i][j] == 'W')
                    dfs(i, j, ++ponds);
        printf("%d\n", ponds);
    }
    return 0;
}

複雜度與變體

• 時間 O(N*M)，每個格子訪問常數次。
• 空間 O(N*M) 存網格與標記。
• 可改用 BFS 避免遞歸棧溢出（此處規模小無妨）。
• 四連通版本只需修改方向數組為上下左右。