日期：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")
