ZeroJudge 解題筆記：c129. 00572 - Oil Deposits

作者：王一哲
日期：2026年3月21日


ZeroJudge 題目連結：c129. 00572 - Oil Deposits

解題想法

這類連通區塊的題目用 BFS 就對了。但是這題的連通方式跟踩地雷一樣，有 8 個方向要檢查。

Python 程式碼

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

import sys
from collections import deque

for line in sys.stdin:
    if not line.strip(): continue
    m, n = map(int, line.split())  # 地圖尺寸 m*n
    if m == 0 and n == 0: break  # 中止迴圈
    grid = [list(sys.stdin.readline().strip()) + ['*'] for _ in range(m)]  # 地圖最右邊加 * 當作哨兵
    grid.append(['*']*(n+1))  # 地圖最下方加 * 當作哨兵
    cnt = 0  # 連通區域數量
    """ BFS """
    for i in range(m):  # 依序掃過地圖每一格，不包含哨兵
        for j in range(n):
            if grid[i][j] == '*': continue  # 不含石油，找下一格
            que = deque([(i, j)])  # 待走訪的佇列
            cnt += 1  # 數量加 1
            grid[i][j] = '*'  # 此格已走訪，設定為 *
            while que:  # 如果 que 有資料繼續執行
                r, c = que.popleft()  # 取出 que 最前面的資料
                # 注意，這題的連通方式跟踩地雷一樣，有 8 個方向要檢查
                for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
                    nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                    if grid[nr][nc] == '*': continue  # 不含石油，找下一格
                    grid[nr][nc] = '*'  # 此格已走訪，設定為 *
                    que.append((nr, nc))  # (nr, nc) 加到 que
    """ End of BFS """
    sys.stdout.write(f"{cnt:d}\n")

C++ 程式碼

使用時間約為 1 ms，記憶體約為 304 kB，通過測試。

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

int main() {
    int m, n;  // 地圖尺寸 m*n
    while(scanf("%d %d", &m, &n) != EOF && (m != 0 || n != 0)) {
        char grid[m+2][n+2];  // 地圖周圍加 * 當作哨兵
        for(int c=0; c<n+2; c++) {
            grid[0][c] = '*';
            grid[m+1][c] = '*';
        }
        for(int r=1; r<m+1; r++) {
            scanf("%s", grid[r]+1);
            grid[r][0] = '*';
            grid[r][n+1] = '*';
        }
        int cnt = 0;  // 連通區域數量
        /* BFS 注意，這題的連通方式跟踩地雷一樣，有 8 個方向要檢查 */
        int dr[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dc[8] = {1, 1, 0, -1, -1, -1, 0, 1};
        for(int i=1; i<=m; i++) {  // 依序掃過地圖每一格，不包含哨兵
            for(int j=1; j<=n; j++) {
                if (grid[i][j] == '*') continue;  // 不含石油，找下一格
                queue<pair<int, int>> que;  // 待走訪的佇列
                que.push(make_pair(i, j));
                cnt++;  // 數量加 1
                grid[i][j] = '*';  // 此格已走訪，設定為 *
                while(!que.empty()) {  // 如果 que 有資料繼續執行
                    int r = que.front().first, c = que.front().second;  // 取出 que 最前面的資料
                    que.pop();
                    for(int k=0; k<8; 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
                    }
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}