日期：2026年4月29日
ZeroJudge 題目連結：d191. 11352 - Crazy King
解題想法
因為我不想要在檢查騎士可以走到的位置時，需要先檢查這一步是不會出界，我會在地圖的周圍加上兩層 $-1$ 當作哨兵，用 $-1$ 標示邊界及不能走到的格子，假設地圖尺寸原為 $m \times n$，如果用 Python 解題會改成尺寸為 $(m+2) \times (n+2)$ 的二維串列，如果用 C++ 解題會改成尺寸為 $(m+4) \times (n+4)$ 的二維陣列。地圖 $grid$ 之中實際上儲存的是步數，用 $0$ 代表起點，$-2$ 代表終點，$-3$ 代表空格及未走過的格子，$-1$ 代表邊界及不能走的格子。讀取地圖資料，依照字元標示 $grid$ 的數字，再檢查騎士的位置，將騎士可以一步走到的格子也標示成 $-1$。最後再用 BFS，找出國王從 $A$ 點走到 $B$ 點的最少步數。BFS 結束之後，如果終點對應的格子仍為 $-2$，代表無法走到終點。
Python 程式碼
使用時間約為 24 ms，記憶體約為 9.2 MB，通過測試。
from collections import deque
t = int(input())
for _ in range(t):
""" 讀取地圖資料 """
m, n = map(int, input().split()) # 棋盤 m*n，實際上儲存的是步數
grid = [[-1]*(n+2) for _ in range(m+2)] # 最右側、最下方加上兩層 -1 當作哨兵
knight = [] # 騎士的位置
sr, sc, er, ec = 0, 0, 0, 0 # 起點、終點
for r in range(m): # 讀取 m 行資料
line = input()
for c, ch in enumerate(line): # 依序讀取 line 的字元
if ch == 'Z': knight.append((r, c)) # 騎士
elif ch == 'A': # 起點
grid[r][c] = 0; sr = r; sc = c;
elif ch == 'B': # 終點
grid[r][c] = -2; er = r; ec = c;
elif ch == '.': # 空格
grid[r][c] = -3
for r, c in knight: # 依序讀取騎士所在的位置
# 依序檢查右上、右、右下、下、左下、左、左上、上
for dr, dc in ((-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)):
nr, nc = r+dr, c+dc # 檢查 (nr, nc)
if grid[nr][nc] == -3: # 空格
grid[nr][nc] = -1 # 設定成 -1，不能走
""" BFS 找最短路徑 """
que = deque([(sr, sc)]) # 待走訪佇列
end = False
while que and not end: # 如果 que 還有資料而且還沒有走到終點，繼續執行
r, c = que.popleft() # 取出 que 最前面的資料
# 依序檢查右上、右、右下、下、左下、左、左上、上
for dr, dc in ((-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0)):
nr, nc = r+dr, c+dc # 檢查 (nr, nc)
if grid[nr][nc] == -3: # 走到空格
grid[nr][nc] = grid[r][c] + 1 # 更新步數
que.append((nr, nc)) # (nr, nc) 加到 que
elif grid[nr][nc] == -2: # 走到終點
grid[nr][nc] = grid[r][c] + 1 # 更新步數
end = True; break # 走到終點，中止迴圈
""" 印出答案 """
if grid[er][ec] == -2: # 無法走到終點
print("King Peter, you can't go now!")
else: # 走到終點
print(f"Minimal possible length of a trip is {grid[er][ec]:d}")
