/*BFS，注意马脚！马脚WA了一次，后来WA了N次，最后发现输入时候将军和马的位置搞反，更改后AC*/
1 #include<stdio.h> 2 #include<queue> 3 #include<string.h> 5 using namespace std; 6 const int maxn=10000,maxm=25; 7 int vis[maxm][maxm],m,n; 8 int dir[10][3]={{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2}},hind[5][3]={{1,0},{0,-1},{-1,0},{0,1}}; 9 struct node{10     int xpos;11     int ypos;12     int step;13     void init(int x,int y,int z)14     {15         xpos=x;16         ypos=y;17         step=z;18     }19 };20 int is_ok(int x,node sour,node tar)21 {22       if(x<=1){23         if(sour.xpos+1==tar.xpos && sour.ypos==tar.ypos)24             return 0;25       }26       else if(x<=3){27         if(sour.xpos==tar.xpos && sour.ypos-1==tar.ypos)28             return 0;29       }30       else if(x<=5){31         if(sour.xpos-1==tar.xpos && sour.ypos==tar.ypos)32             return 0;33       }34       else if(x<=7){35         if(sour.xpos==tar.xpos && sour.ypos+1==tar.ypos)36             return 0;37       }38       return 1;39 }40 int bfs(node source,node target);41 int main()42 {43     node source,target;44     while(~scanf("%d%d%d%d%d%d",&n,&m,&target.xpos,&target.ypos,&source.xpos,&source.ypos)){45         int minsteps=bfs(source,target);46         printf("%d\n",minsteps);47     }48     return 0;49 }50 int bfs(node source,node target)51 {52     queue<node>q;53     memset(vis,0,sizeof(vis));54     source.step=0;55     q.push(source);57     vis[source.xpos][source.ypos]=1;58     if(source.xpos==target.xpos && source.ypos==target.ypos)59         return 0;60     while(!q.empty()){61         node a=q.front();62         q.pop();63         for(int i=0;i<8;i++){64                 int nx=a.xpos+dir[i][0];65                 int ny=a.ypos+dir[i][1];66                 if(nx<1 || ny<1 || nx>n || ny>m)67                     continue;68                 if(!is_ok(i,a,target))69                     continue;70                 if(vis[nx][ny])71                     continue;72                 if(nx==target.xpos && ny==target.ypos)73                     return a.step+1;74                 node c;75                 c.init(nx,ny,a.step+1);76                 q.push(c);77                 vis[nx][ny]=1;78         }79     }80     return -1;81 }