ZeroJudge 解題筆記：c117. 00439 - Knight Moves

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


ZeroJudge 題目連結：c117. 00439 - Knight Moves

解題想法

為了便於計算，會將棋盤的座標改成 0-indexed。用一個二維串列記錄從起點走到每一格的步數，預設值 -1 代表未走訪，起點步數為 0，用 BFS 找步數。

Python 程式碼

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

import sys
from collections import deque

result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    start, end = data[ptr:ptr+2]  # 起點，終點
    ptr += 2
    if start == end:  # 特例，不需要移動
        result.append(f"To get from {start:s} to {end:s} takes 0 knight moves.\n")
        continue
    grid = [[-1]*8 for _ in range(8)]  # 棋盤上走到每格的步數，-1 代表還沒有走過
    c1 = ord(start[0]) - ord('a')  # 起點座標 (r1, c1)，改成 0-index
    r1 = int(start[1]) - 1
    c2 = ord(end[0]) - ord('a')  # 終點座標 (r2, c2)，改成 0-index
    r2 = int(end[1]) - 1
    grid[r1][c1] = 0  # 起點步數 0
    que = deque([(r1, c1)])  # 待走訪佇列
    find_ans = False  # 是否找到答案
    while que and not find_ans:  # BFS，如果 que 還有資料而且還沒有找到答案，繼續執行
        r, c = que.popleft()  # 目前所在的位置 (r, c)
        for dr, dc in ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)):  # 八方位檢查
            nr, nc = r+dr, c+dc  # 正在檢查 (nr, nc)
            if 0 <= nr < 8 and 0 <= nc < 8 and grid[nr][nc] == -1:  # 未出界也未走訪
                grid[nr][nc] = grid[r][c] + 1  # 更新 (nr, nc) 的步數
                if nr == r2 and nc == c2:  # 走到終點
                    find_ans = True  # 已經找到答案
                    break  # 中止迴圈
                que.append((nr, nc))  # 將 (nr, nc) 加入 que
    result.append(f"To get from {start:s} to {end:s} takes {grid[r2][c2]:d} knight moves.\n")
sys.stdout.write("".join(result))

C++ 程式碼

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

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

int main() {
    char start[3], end[3];  // 起點，終點
    while(scanf(" %s %s", start, end) != EOF) {
        int c1 = start[0]-'a', r1 = start[1]-'1';  // 起點座標 (r1, c1)
        int c2 = end[0]-'a', r2 = end[1]-'1';  // 終點座標 (r2, c2)
        if (c1 == c2 && r1 == r2) {  // 特例，不需要移動
            printf("To get from %s to %s takes 0 knight moves.\n", start, end);
            continue;
        }
        int grid[8][8];  // 棋盤上走到每格的步數，周圍加兩層 -1 作為哨兵
        memset(grid, -1, sizeof(grid));
        grid[r1][c1] = 0;
        queue<pair<int, int>> que;  // 待走訪佇列
        que.push(make_pair(r1, c1));  // que 先加入 (r1, c1)
        bool find_ans = false;  // 是否找到答案
        int dr[8] = {1, 2, 2, 1, -1, -2, -2, -1}, dc[8] = {2, 1, -1, -2, -2, -1, 1, 2};  // 八方位檢查用的位移量
        while(!que.empty() && !find_ans) {  // BFS，如果 que 還有資料而且還沒有找到答案，繼續執行
            int r = que.front().first, c = que.front().second;  // 目前所在的位置 (r, c)
            que.pop();
            for(int i=0; i<8; i++) {  // 八方位檢查
                int nr = r+dr[i], nc = c+dc[i];  // 正在檢查 (nr, nc)
                if (nr >= 0 && nr < 8 && nc >= 0 && nc < 8 && grid[nr][nc] == -1) {  // 未出界也未走訪
                    grid[nr][nc] = grid[r][c] + 1;  // 更新 (nr, nc) 的步數
                    if (nr == r2 && nc == c2) {  // 走到終點
                        find_ans = true;  // 已經找到答案
                        break;  // 中止迴圈
                    }
                    que.push(make_pair(nr, nc));  // 將 (nr, nc) 加入 que
                }
            }
        }
        printf("To get from %s to %s takes %d knight moves.\n", start, end, grid[r2][c2]);
    }
    return 0;
}