NYoj-27 水池計數：DFS 與 BFS 完整解析

NYoj-27 水池數目 - 連通塊統計經典題

給定一個 m x n 的地圖矩陣，1 代表水池，0 代表陸地。相鄰（上下左右）的水池視為同一個水池。求地圖中水池的總數。這是典型的「島嶼數量」問題，核心在於圖的連通分量統計。

深度優先搜索 (DFS) 實現

DFS 利用遞歸或棧將一個水池所有相連的 '1' 標記為 '0'（或訪問標記），每發起一次 DFS，計數器加一。提供兩種寫法：

寫法一：直接展開四個方向

void DFS(int i, int j) {
    if(map[i][j-1]) { map[i][j-1]=0; DFS(i, j-1); }
    if(map[i][j+1]) { map[i][j+1]=0; DFS(i, j+1); }
    if(map[i-1][j]) { map[i-1][j]=0; DFS(i-1, j); }
    if(map[i+1][j]) { map[i+1][j]=0; DFS(i+1, j); }
}

寫法二：方向數組優化（推薦）

int f[4][2] = {{-1,0}, {1,0}, {0,1}, {0,-1}};
void DFS(int i, int j) {
    map[i][j] = 0;
    for(int k=0; k<4; k++) {
        int ni = i + f[k][0], nj = j + f[k][1];
        if(map[ni][nj] == 1) DFS(ni, nj);
    }
}

廣度優先搜索 (BFS) 實現

BFS 使用隊列模擬「波浪式」擴散，避免遞歸棧溢出風險，適合大數據範圍。

struct Node { int x, y; };
queue q;
void BFS(int i, int j) {
    q.push({i, j}); map[i][j] = 0;
    while(!q.empty()) {
        Node cur = q.front(); q.pop();
        for(int k=0; k<4; k++) {
            int nx = cur.x + f[k][0], ny = cur.y + f[k][1];
            if(map[nx][ny]) { map[nx][ny] = 0; q.push({nx, ny}); }
        }
    }
}

複雜度與注意事項

• 時間複雜度：O(m*n)，每個格子最多被訪問一次。
• 空間複雜度：DFS 取決於遞歸深度（最壞 O(m*n)），BFS 取決於隊列大小（最壞 O(min(m,n))）。
• 數組開到 [200][200] 足夠應對 m,n < 100 的限制，邊界處理可通過擴展邊界或判斷坐標合法性解決。