利用BFS，每次皆將目前位置的所有8種可能的走法中符合條件(不可超出棋盤)的放入queue中。queue中的資料型態為pos，用以存每次走到的位置及步數。
再放入queue前先檢查是否與目標位置相同，若相同則跳出BFS迴圈。
每次BFS從queue的front所存的位置開始走。
Source Code(C++):
#include<iostream>
#include<string>
#include<queue>
using namespace std;
class pos{
public:
pos() = default;
pos(int a,int b,int c):x(a),y(b),mov(c){
}
void set(int a,int b,int c){
x = a;
y = b;
mov = c;
}
friend bool operator ==(const pos &a,const pos &b){
return (a.x == b.x && a.y == b.y);
}
void operator =(const pos &b){
x = b.x;
y = b.y;
mov = b.mov;
}
int x,y;
int mov;
};
int main(){
string a,b;
while(cin>>a>>b){
int mov = 0;
/*int board[8][8];
for(int row = 0;row<8;row++){
for(int col = 0;col<8;col++)
board[row][col] = 0;
}*/ //no need to build a 2D array for the chess board
int a1 = (int)a[0]-97,a2 = (int)a[1]-49;
int b1 = (int)b[0]-97,b2 = (int)b[1]-49;//change the input value to corresponding position on the board
queue<pos> q;
pos temp(a1,a2,0),des(b1,b2,0);
q.push(pos(a1,a2,0) );
while(1){ //BFS loop
if(q.empty() )
break;
temp = q.front();
q.pop();
mov = temp.mov;
if(temp == des || mov > 64)
break;
if(temp.x-2 > -1 && temp.y+1 < 8){//list all 8 possile ways of knight moves
if(temp.x-2 == des.x && temp.y+1 == des.y){
mov = temp.mov+1;
break;
}
q.push(pos(temp.x-2,temp.y+1,temp.mov+1) );
}
if(temp.x-2 > -1 && temp.y-1 > -1){
if(temp.x-2 == des.x && temp.y-1 == des.y){
mov = temp.mov+1;
break;
}
q.push(pos(temp.x-2,temp.y-1,temp.mov+1) );
}
if(temp.x+2 < 8 && temp.y+1 < 8){
if(temp.x+2 == des.x && temp.y+1 == des.y){
mov = temp.mov+1;
break;
}
q.push(pos(temp.x+2,temp.y+1,temp.mov+1) );
}
if(temp.x+2 < 8 && temp.y-1 > -1){
if(temp.x+2 == des.x && temp.y-1 == des.y){
mov = temp.mov+1;
break;
}
q.push(pos(temp.x+2,temp.y-1,temp.mov+1) );
}
if(temp.x-1 > -1 && temp.y+2 < 8){
if(temp.x-1 == des.x && temp.y+2 == des.y){
mov = temp.mov+1;
break;
}
q.push(pos(temp.x-1,temp.y+2,temp.mov+1) );
}
if(temp.x+1 < 8 && temp.y+2 < 8){
if(temp.x+1 == des.x && temp.y+2 == des.y){
mov = temp.mov+1;
break;
}
q.push(pos(temp.x+1,temp.y+2,temp.mov+1) );
}
if(temp.x-1 > -1 && temp.y-2 > -1){
if(temp.x-1 == des.x && temp.y-2 == des.y){
mov = temp.mov+1;
break;
}
q.push(pos(temp.x-1,temp.y-2,temp.mov+1) );
}
if(temp.x+1 < 8 && temp.y-2 > -1){
if(temp.x+1 == des.x && temp.y-2 == des.y){
mov = temp.mov+1;
break;
}
q.push(pos(temp.x+1,temp.y-2,temp.mov+1) );
}
}
cout<<"To get from "<<a<<" to "<<b<<" takes "<<mov<<" knight moves."<<endl;
}
return 0;
}
