在n*n的国际象棋棋盘中，给定一“马(Knight)”和一“后(Queen)”的位置，问“马”能否在m步之内（包括m步）到达“后”的位置？马的走法是：每步棋先横走或直走一格，然后再斜走一格，即走“日”字，没有“中国象棋”中“蹩马腿”的限制。比如在8*8的棋盘中，马的位置为(3, 5)，则下一步可以落在(1 ,6)、(1, 4)、(2, 7)、(2, 3)、(4, 7)、(4, 3)、(5, 6)或(5, 4)。

输入

输入数据有3行，第一行为2个正整数n和m（n <=1000000，m<=256）；第二行为2个正整数kx和ky，代表“马”所在的位置（1<=kx, ky<=n）；第三行为2个正整数qx和qy，代表“后”所在的位置（1<=qx, qy<=n）。我们保证马和后的位置不会重叠。

如果“马”能够在m步之内（包括m步）到达“后”的位置，则输出：
Knight can reach Queen within m moves!

否则输出：
Knight cannot reach Queen within m moves!

其中m为给定的马步数。

 #include<stdio.h>

 #include<queue>

 #include<set>

 using namespace std;

 int abs(int x){return x>=?x:-x;}

 struct point{int x,y,k;}s,e;

 int n,m;

 int dx[]={,,,,-,-,-,-};

 int dy[]={-,-,,,,,-,-};

 int bfs()

 {

     if(abs(s.x-e.x)/>m)return ;//x不行

     if(abs(s.y-e.y)/>m)return ;//y不行

     point h,t;

     queue<point> qu;

     set<__int64> se;//哈希1000000

     __int64 hs=((__int64)s.x)*+(__int64)s.y;

     se.insert(hs);

     s.k=;

     qu.push(s);

     while(!qu.empty())

     {

         h=qu.front();

         qu.pop();

         if(h.x==e.x&&h.y==e.y)

             return ;

         if(h.k==m)continue;//步数不超限

         for(int i=;i<;i++)

         {

             t.x=h.x+dx[i];

             t.y=h.y+dy[i];

             if(t.x==e.x&&t.y==e.y)//找到赶紧跳出

                 return ;

             hs=((__int64)t.x)*+(__int64)t.y;

             if(t.x>=&&t.x<=n&&t.y>=&&t.y<=n&&se.find(hs)==se.end())

             {

                 t.k=h.k+;

                 se.insert(hs);

                 qu.push(t);

             }

         }

     }

     return ;

 }

 int main(){

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y);

         if(bfs())printf("Knight can reach Queen within %d moves!\n",m);

         else printf("Knight cannot reach Queen within %d moves!\n",m);

     }

     return ;

 }