日期：2026年10月23日
ZeroJudge 題目連結：p920.塗鴉連線 (Doodle)
題目 pdf 檔連結：塗鴉連線 (Doodle)
解題想法
每組測資第一列為兩個整數 $m$、$n$，代表地圖尺寸為 $m \times n$，接下來 $m$ 列每列有 $n$ 個數字，$1$ 代表這格有塗黑，$0$ 代表這格沒有塗黑。起點為左上角 $(0, 0)$，終點為右下角 $(m-1, n-1)$，這兩格都是 $1$，而且只與另一格 $1$ 相鄰；起點、終點路徑上其它的 $1$ 則會與另外 $2$ 格 $1$ 相鄰。計算從起點到終點移動的格子數量。
我習慣用 BFS 處理這類型走格子的題目，但是這題並不需要用到 BFS，因為起點、終點路徑上其它的 $1$ 則會與另外 $2$ 格 $1$ 相鄰，假設已經走過的格子被標記為 $0$，用四方位檢查找出與這格相鄰的 $1$ 時只會找到 $1$ 格，只要找到這格就可以再往下走。
Python 程式碼
使用時間約為 16 ms，記憶體約為 10 MB，通過測試。
def solve():
import sys
from collections import deque
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
# 讀取測資
m = int(data[ptr])
n = int(data[ptr + 1])
ptr += 2
grid = []
for _ in range(m):
row = list(map(int, data[ptr : ptr + n]))
ptr += n
grid.append(row)
# 用 BFS 找步數
que = deque([(0, 0, 1)]) # 起點 (0, 0)，步數 1
grid[0][0] = 0 # 改成 0，標記為已走過
while que:
r, c, s = que.popleft()
if r == m - 1 and c == n - 1: # 走到終點
result.append(f"{s:d}\n")
break
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 0
que.append((nr, nc, s + 1))
# 一次輸出所有答案
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
