Knight Moves

题意：给定象棋棋盘上的两个位置a，b，计算马从a到b所需要的步数的最小值。
题解：把整个棋盘看成一个二维的图，a，b相当于两个点，然后做bfs即可
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 struct Node{
  8  int x;
  9  int y;
 10  int step;
 11 }; //记录当前节点的坐标以及到起点的步数
 12 
 13 int map[9][9]; //记录地图
 14 int sx,sy,dx,dy;//记录起点和目标的坐标
 15 int mit[10][10]; //mit【i】【j】，记录i，j的点到起点的最小步数。
 16 int bfs(){
 17      queue<Node> Q;
 18       Node temp;
 19       temp.x=sx;
 20       temp.y=sy;
 21       temp.step=0;
 22     Q.push(temp);
 23     while(!Q.empty()){
 24       Node tmp;
 25       tmp=Q.front();
 26       Q.pop();
 27       int xx=tmp.x;
 28       int yy=tmp.y; //以下从当前节点向周围8个方向进行收索
 29       if(xx-2>=1&&yy+1<=8&&tmp.step+1<mit[xx-2][yy+1]){
 30               mit[xx-2][yy+1]=tmp.step+1;  //如果到下一个节点的步数小于以前已经记录的值
 31               Node tt;                 //注意边界的处理
 32               tt.x=xx-2;
 33               tt.y=yy+1;
 34               tt.step=tmp.step+1;
 35               Q.push(tt);
 36         }
 37         if(xx-1>=1&&yy+2<=8&&tmp.step+1<mit[xx-1][yy+2]){
 38               mit[xx-1][yy+2]=tmp.step+1;
 39               Node tt;
 40               tt.x=xx-1;
 41               tt.y=yy+2;
 42               tt.step=tmp.step+1;
 43               Q.push(tt);
 44         }
 45          if(xx+1<=8&&yy+2<=8&&tmp.step+1<mit[xx+1][yy+2]){
 46               mit[xx+1][yy+2]=tmp.step+1;
 47               Node tt;
 48               tt.x=xx+1;
 49               tt.y=yy+2;
 50               tt.step=tmp.step+1;
 51               Q.push(tt);
 52         }
 53          if(xx+2<=8&&yy+1<=8&&tmp.step+1<mit[xx+2][yy+1]){
 54               mit[xx+2][yy+1]=tmp.step+1;
 55               Node tt;
 56               tt.x=xx+2;
 57               tt.y=yy+1;
 58               tt.step=tmp.step+1;
 59               Q.push(tt);
 60         }
 61            if(xx+2<=8&&yy-1>=1&&tmp.step+1<mit[xx+2][yy-1]){
 62               mit[xx+2][yy-1]=tmp.step+1;
 63               Node tt;
 64               tt.x=xx+2;
 65               tt.y=yy-1;
 66               tt.step=tmp.step+1;
 67               Q.push(tt);
 68         }
 69           if(xx+1<=8&&yy-2>=1&&tmp.step+1<mit[xx+1][yy-2]){
 70               mit[xx+1][yy-2]=tmp.step+1;
 71               Node tt;
 72               tt.x=xx+1;
 73               tt.y=yy-2;
 74               tt.step=tmp.step+1;
 75               Q.push(tt);
 76         }
 77          if(xx-1>=1&&yy-2>=1&&tmp.step+1<mit[xx-1][yy-2]){
 78               mit[xx-1][yy-2]=tmp.step+1;
 79               Node tt;
 80               tt.x=xx-1;
 81               tt.y=yy-2;
 82               tt.step=tmp.step+1;
 83               Q.push(tt);
 84         }
 85         if(xx-2>=1&&yy-1>=1&&tmp.step+1<mit[xx-2][yy-1]){
 86               mit[xx-2][yy-1]=tmp.step+1;
 87               Node tt;
 88               tt.x=xx-2;
 89               tt.y=yy-1;
 90               tt.step=tmp.step+1;
 91               Q.push(tt);
 92         }
 93 
 94 
 95 
 96     }
 97      return mit[dx][dy];
 98 
 99 }
100 int main(){
101     char s1[3];
102     char s2[3];
103 while(~scanf("%s %s",s1,s2)){//读取两个字符
104     for(int i=1;i<=8;i++)
105       for(int j=1;j<=8;j++){
106       mit[i][j] =10000000; //这里记住初始化，memset不管用
107       }
108      sy=s1[0]-96;//小写字母转化成数字
109      sx=s1[1]-48;//数字字符转化成int类型的数字
110      dy=s2[0]-96;
111      dx=s2[1]-48;
112      mit[sx][sy]=0;//初始化
113     int ans=bfs();
114      printf("To get from %s to %s takes %d knight moves.
",s1,s2,ans);
115 }
116 }
View Code