# 【題解】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