【題解】ZeroJudge c117: 00439 – Knight Moves

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c117
【解題想法】BFS

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int dis[8][8], d[8][2] = {{2, 1}, {2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
string s, t;

bool check(int x, int y){
    if (0 <= x && x < 8 && 0 <= y && y < 8){
        if (dis[x][y] == -1) return true;
    }
    return false;
}

int main() {
    while (cin >> s >> t){
        pair<int, int> start = {s[0]-'a', s[1]-'1'}, goal = {t[0]-'a', t[1]-'1'};
        memset(dis, -1, sizeof(dis));
        queue <pair<int, int> > q;
        q.push(start);
        dis[start.first][start.second] = 0;
        while (!q.empty()){
            int x = q.front().first, y = q.front().second;
            q.pop();
            for (int i = 0; i < 8; i++){
                if (check(x+d[i][0], y+d[i][1])){
                    q.push({x+d[i][0], y+d[i][1]});
                    dis[x+d[i][0]][y+d[i][1]] = dis[x][y]+1;
                }
            }
            if (dis[goal.first][goal.second] != -1) break;
        }
        cout << "To get from " << s << " to " << t << " takes " << dis[goal.first][goal.second] << " knight moves.\n";
    }
}

Python code (credit: Amy Chou)

dx = [2, 2, -2, -2, 1, 1, -1, -1]
dy = [1, -1, 1, -1, 2, -2, 2, -2]
        
while True:
    try:
        s1, s2 = map(str, input().split())
        if s1 == s2:
            print(f"To get from {s1} to {s2} takes 0 knight moves.")
        else:
            x1 = ord(s1[0]) - ord('a')
            y1 = int(s1[1]) - 1
            x2 = ord(s2[0]) - ord('a')
            y2 = int(s2[1]) - 1
            
            
            q = [(x1, y1, 0)]
            flag = False
            while q:
                x, y, step = q[0][0], q[0][1], q[0][2]
                q.pop(0)
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx == x2 and ny == y2:
                        flag = True
                        print(f"To get from {s1} to {s2} takes {step+1} knight moves.")
                        break
                    if nx >= 0 and nx < 8 and ny >= 0 and ny < 8:
                        q.append((nx, ny, step+1))
                if flag:
                    break
    except:
        break

分享本文 Share with friends