日期：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}")
C++ 程式碼
使用時間約為 1 ms，記憶體約為 3.5 MB，通過測試。
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; // t 筆測資
// 檢測騎士、國王周圍 8 格的位移量
int dr[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dc[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dr2[8] = {-1, 0, 1, 1, 1, 0, -1, -1}, dc2[8] = {1, 1, 1, 0, -1, -1, -1, -0};
while(t--) {
/* 讀取地圖資料 */
int m, n; cin >> m >> n; // 棋盤 m*n，實際上儲存的是步數
vector<vector<int>> grid (m+4, vector<int> (n+4, -1)); // 周圍加兩層 -1 當作哨兵
vector<pair<int, int>> knight; // 騎士的位置
int sr = 0, sc = 0, er = 0, ec = 0; // 起點、終點
for(int r=2; r<m+2; r++) { // 讀取 m 行資料
string line; cin >> line;
for(int i=0; i<n; i++) { // 依序讀取 line 的字元
int c = i+2;
char ch = line[i];
if (ch == 'Z') { // 騎士
knight.push_back(make_pair(r, c));
} else if (ch == 'A') { // 起點
grid[r][c] = 0; sr = r; sc = c;
} else if (ch == 'B') { // 終點
grid[r][c] = -2; er = r; ec = c;
} else if (ch == '.') { // 空格
grid[r][c] = -3;
}
}
}
for(auto pos : knight) { // 依序讀取騎士所在的位置
int r = pos.first, c = pos.second;
// 依序檢查右上、右、右下、下、左下、左、左上、上
for(int i=0; i<8; i++) {
int nr = r+dr[i], nc = c+dc[i]; // 檢查 (nr, nc)
if (grid[nr][nc] == -3) { // 空格
grid[nr][nc] = -1; // 設定成 -1，不能走
}
}
}
/* BFS 找最短路徑 */
queue<pair<int, int>> que; // 待走訪佇列
que.push(make_pair(sr, sc));
bool end = false;
while(!que.empty() && !end) { // 如果 que 還有資料而且還沒有走到終點，繼續執行
int r = que.front().first, c = que.front().second; // 取出 que 最前面的資料
que.pop();
// 依序檢查右上、右、右下、下、左下、左、左上、上
for(int i=0; i<8; i++) {
int nr = r+dr2[i], nc = c+dc2[i]; // 檢查 (nr, nc)
if (grid[nr][nc] == -3) { // 走到空格
grid[nr][nc] = grid[r][c] + 1; // 更新步數
que.push(make_pair(nr, nc)); // (nr, nc) 加到 que
} else if (grid[nr][nc] == -2) { // 走到終點
grid[nr][nc] = grid[r][c] + 1; // 更新步數
end = true; break; // 走到終點，中止迴圈
}
}
}
/* 印出答案 */
if (grid[er][ec] == -2) { // 無法走到終點
cout << "King Peter, you can't go now!\n";
} else { // 走到終點
cout << "Minimal possible length of a trip is " << grid[er][ec] << "\n";
}
}
return 0;
}
沒有留言:
張貼留言