1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 6 int IsVis[9][9];//记录位置是否被访问 7 int StaX,StaY,EndX,EndY; 8 char Start[3],End[3]; //起始及结束位置 9 typedef struct node 10 { 11 int x,y,MoveNum; 12 }knight; 13 int Move[8][2]={-1,2, -2,1, 2,1, 1,-2, 1,2, 2,-1, -1,-2, -2,-1};//骑士的移动方位 14 void Bfs(int x,int y); 15 16 int main(){ 17 //freopen("D:\t.txt","r",stdin); 18 while(cin>>Start>>End){ 19 StaX = Start[0] - 'a' + 1; 20 StaY = Start[1] - '0'; 21 EndX = End[0] - 'a' + 1; 22 EndY = End[1] - '0';//对输入的棋子的位置进行处理 23 Bfs(StaX,StaY); 24 } 25 return 0; 26 } 27 void Bfs(int x,int y){ 28 knight m,n; 29 queue<knight> Que; 30 31 m.x = x; 32 m.y = y; 33 m.MoveNum = 0; 34 memset(IsVis,0,sizeof(IsVis));//每一回合棋盘初始化 35 IsVis[m.x][m.y] = 1; 36 Que.push(m); 37 while(!Que.empty()){ 38 m = Que.front(); 39 Que.pop(); 40 if(m.x == EndX&&m.y == EndY){ 41 cout<<"To get from "<<Start[0]<<Start[1]<<" to "<<End<<" takes "<<m.MoveNum<<" knight moves."<<endl; 42 break; 43 }//如果到达结束位置，结束 44 for(int i = 0;i < 8;i++){ 45 if((m.x + Move[i][0] > 0) && (m.x + Move[i][0] < 9) && (m.y + Move[i][1] > 0) && (m.y + Move[i][1] < 9) 46 && !IsVis[m.x + Move[i][0]][m.y + Move[i][1]]){//判断移动是否超范围及是否被访问 47 n.x = m.x + Move[i][0]; 48 n.y = m.y + Move[i][1]; 49 n.MoveNum = m.MoveNum + 1; 50 Que.push(n); 51 } 52 } 53 } 54 55 }
题目说的是骑士从一个位置移动到另一个位置所需的步数，国际象棋里骑士移动和中国象棋里的马类似，都是“日”形。
题目用bfs求解，要运用到队列，使得骑士走的步数不断更新。以便在bfs过程中，统计的移动步数是最短的。