DescriptionLsXHTML5中文学习网 - HTML5先行者学习网

BackgroundLsXHTML5中文学习网 - HTML5先行者学习网
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?LsXHTML5中文学习网 - HTML5先行者学习网
The ProblemLsXHTML5中文学习网 - HTML5先行者学习网
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.LsXHTML5中文学习网 - HTML5先行者学习网
For people not familiar with chess, the possible knight moves are shown in Figure 1.LsXHTML5中文学习网 - HTML5先行者学习网
LsXHTML5中文学习网 - HTML5先行者学习网

InputLsXHTML5中文学习网 - HTML5先行者学习网

The input begins with the number n of scenarios on a single line by itself.LsXHTML5中文学习网 - HTML5先行者学习网
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

OutputLsXHTML5中文学习网 - HTML5先行者学习网

For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

Sample InputLsXHTML5中文学习网 - HTML5先行者学习网

1 2 3 4 5 6 7 8 9 10

3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1

Sample OutputLsXHTML5中文学习网 - HTML5先行者学习网

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

5 28 0 <strong>题意：给一个N*N的棋盘，并给出起点终点的x y坐标 球起点到终点的最小步数。</strong> 双向BFS代码： <pre class="brush:java;">#include<iostream> #include<cstdio> #include<queue> #include<cstring> #define qq 330 using namespace std; int vis1[qq][qq];      //既标记路径 也统计步数 int vis2[qq][qq]; int fx1[8]={2,2,-2,-2,1,1,-1,-1}; int fx2[8]={1,-1,1,-1,2,-2,2,-2}; struct node {  int x,y; }start,end;               //双向BFS的两端起点      int sx,sy,ex,ey; int m; bool inside(int xx,int yy)           //判断越界 {     if(xx>=0&&yy>=0&&xx<m&&yy<m) return="" true;="" else="" false;="" }="" void="" dbfs()="" {="" int="" i,tq,tw;="" queue<node="">q,w;            //两个队列     start.x=sx;start.y=sy;     end.x=ex;end.y=ey;     q.push(start);     w.push(end);                  vis1[sx][sy]=0;         //后面的步数是从0开始加的     vis2[ex][ey]=0;     while(!q.empty()&&!w.empty())     {         node now,next;         tq=q.size();      //为了先将一个队列的全部判断完         while(tq--)         {           now=q.front();           q.pop();           if(inside(now.x,now.y)&&vis2[now.x][now.y]!=-1)    //两端开始的都经过这一点。。           {               printf("%dn",vis1[now.x][now.y]+vis2[now.x][now.y]);               return;           }           for(i=0;i<8;i++)           {               next.x=now.x+fx1[i];               next.y=now.y+fx2[i];               if(inside(next.x,next.y)&&vis2[next.x][next.y]!=-1)    //重要，，因为奇数步时。。。               {                   printf("%dn",vis1[now.x][now.y]+1+vis2[next.x][next.y]);                   return;               }               if(inside(next.x,next.y)&&vis1[next.x][next.y]==-1)               {                   vis1[next.x][next.y]=vis1[now.x][now.y]+1;                   q.push(next);               }           }         }         tw=w.size();         while(tw--)        //同上         {           now=w.front();           w.pop();           if(inside(now.x,now.y)&&vis1[now.x][now.y]!=-1)           {               printf("%dn",vis1[now.x][now.y]+vis2[now.x][now.y]);               return;           }           for(i=0;i<8;i++)           {               next.x=now.x+fx1[i];               next.y=now.y+fx2[i];               if(inside(next.x,next.y)&&vis1[next.x][next.y]!=-1)               {                   printf("%dn",vis2[now.x][now.y]+1+vis1[next.x][next.y]);                   return;               }               if(inside(next.x,next.y)&&vis2[next.x][next.y]==-1)               {                   vis2[next.x][next.y]=vis2[now.x][now.y]+1;                   w.push(next);               }           }         }     } } int main() {     int t;     scanf("%d",&t);     while(t--)     {         scanf("%d",&m);         scanf("%d%d%d%d",&sx,&sy,&ex,&ey);         memset(vis1,-1,sizeof(vis1));      //标记为未走过         memset(vis2,-1,sizeof(vis2));         dbfs();     }         return 0; } </m&&yy<m)></cstring></queue></cstdio></iostream></pre><br>双向BFS的精髓在于从起点终点同时开始搜索 当找到一点同时两端都经过时 即找到最短路径。。<br><br>