ZeroJudge 解題筆記：f493. 水窪問題

作者：王一哲
日期：2025年10月13日


ZeroJudge 題目連結：f493. 水窪問題

解題想法

這類型的題目我習慣用 BFS 解題，已走訪的位置改成題目給的陸地符號 #，不需要另外開一個陣列儲存已走訪的位置，可以節省一些記憶體。

Python 程式碼

使用時間約為 0.3 s，記憶體約為 11.1 MB，通過測試。

from collections import deque

n, m = map(int, input().split())  # 地圖 n*m
grid = [list(input() + "#") for _ in range(n)]  # 讀取地圖資料，右側加上 #
grid.append(["#"]*(n+1))  # 最下方加上 n+1 個 #
cnt, imin, imax = 0, float('inf'), 0  # 數量，最小面積、最大面積
### BFS ###
for i in range(n):  # 依序掃過每一格
    for j in range(m):
        if grid[i][j] == "#": continue  # 如果是 #，找下一格
        grid[i][j] = "#"  # 此格改成 #
        cnt += 1  # 數量加 1
        area = 0  # 這個水漥的面積
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列 que
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭取出座標 (r, c)
            area += 1  # 面積加 1
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] == "#": continue  # 如果是 #，找下一格
                grid[nr][nc] = "#"  # 此格改成 #
                que.append((nr, nc))  # (nr, nc) 加入 que
        imin = min(imin, area)  # 更新 imin
        imax = max(imax, area)  # 更新 imax
### 結束 BFS ###
if cnt == 0:  # 如果 cnt 等於 0，印出 0 0 0
    print("0 0 0")
else:  # 反之印出 imax, imin, cnt
    print(imax, imin, cnt)

C++ 程式碼

使用時間約為 11 ms，記憶體約為 1.2 MB，通過測試。

#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    int n, m; scanf("%d %d", &n, &m);  // 地圖 n*m
    char grid[n+2][m+2];  // 地圖資料，四周加上一圈 #
    for(int j=0; j<m+2; j++) {  // 先處理第 0 列及第 n+1 列
        grid[0][j] = '#'; grid[n+1][j] = '#';
    }
    for(int i=1; i<=n; i++) {  // 再處理第 1 ~ n 列
        scanf("%s", &grid[i][1]);  // 先讀取整行資料存入 grid[i][1]
        grid[i][0] = '#'; grid[i][m+1] = '#';  // 再處理第 0 欄及第 m+1 欄
    }
    /* BFS */
    int cnt = 0, imin = 1E7, imax = 0;  // 數量，最小面積、最大面積
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    for(int i=1; i<=n; i++) {  // 依序掃過每一格
        for(int j=1; j<=m; j++) {
            if (grid[i][j] == '#') continue;  // 如果是 #，找下一格
            grid[i][j] = '#';  // 此格改成 #
            cnt++;  // 數量加 1
            int area = 0;  // 這個水漥的面積
            queue<pair<int, int>> que;  // (i, j) 加入待走訪佇列 que
            que.push(make_pair(i, j));
            while(!que.empty()) {  // 如果 que 還有資料繼續執行
                int r = que.front().first, c = que.front().second;  // 從 que 開頭取出座標 (r, c)
                que.pop();
                area++;  // 面積加 1
                for(int k=0; k<4; k++) {  // 四方位檢查
                    int nr = r+dr[k], nc = c+dc[k];  // 要檢查 (nr, nc)
                    if (grid[nr][nc] == '#') continue;  // 如果是 #，找下一格
                    grid[nr][nc] = '#';  // 此格改成 #
                    que.push(make_pair(nr, nc));  // (nr, nc) 加入 que
                }
            }
            imin = min(imin, area);  // 更新 imin
            imax = max(imax, area);  // 更新 imax
        }
    }
       
    /* 結束 BFS */
    if (cnt == 0) {  // 如果 cnt 等於 0，印出 0 0 0
        printf("0 0 0\n");
    } else {  // 反之印出 imax, imin, cnt
        printf("%d %d %d\n", imax, imin, cnt);
    }
    return 0;
}