描述
在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为给定的马步数。
样例输入
8 2
3 5
7 4
样例输出
Knight cannot reach Queen within 2 moves!
题意
马能否在m步之内到后
题解
这题n<=1e6肯定MLE，所以得用广搜，已经到过的点加入队列
这里我把点哈希成1个数字存入set中，方便查找
代码
1 #include<stdio.h> 2 #include<queue> 3 #include<set> 4 using namespace std; 5 6 int abs(int x){return x>=0?x:-x;} 7 struct point{int x,y,k;}s,e; 8 int n,m; 9 int dx[]={1,2,2,1,-1,-2,-2,-1}; 10 int dy[]={-2,-1,1,2,2,1,-1,-2}; 11 int bfs() 12 { 13 if(abs(s.x-e.x)/2>m)return 0;//x不行 14 if(abs(s.y-e.y)/2>m)return 0;//y不行 15 point h,t; 16 queue<point> qu; 17 set<__int64> se;//哈希1000000 18 __int64 hs=((__int64)s.x)*1000000+(__int64)s.y; 19 se.insert(hs); 20 s.k=0; 21 qu.push(s); 22 while(!qu.empty()) 23 { 24 h=qu.front(); 25 qu.pop(); 26 if(h.x==e.x&&h.y==e.y) 27 return 1; 28 if(h.k==m)continue;//步数不超限 29 for(int i=0;i<8;i++) 30 { 31 t.x=h.x+dx[i]; 32 t.y=h.y+dy[i]; 33 if(t.x==e.x&&t.y==e.y)//找到赶紧跳出 34 return 1; 35 hs=((__int64)t.x)*1000000+(__int64)t.y; 36 if(t.x>=1&&t.x<=n&&t.y>=1&&t.y<=n&&se.find(hs)==se.end()) 37 { 38 t.k=h.k+1; 39 se.insert(hs); 40 qu.push(t); 41 } 42 } 43 } 44 return 0; 45 } 46 int main(){ 47 while(scanf("%d%d",&n,&m)!=EOF) 48 { 49 scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y); 50 if(bfs())printf("Knight can reach Queen within %d moves! ",m); 51 else printf("Knight cannot reach Queen within %d moves! ",m); 52 } 53 return 0; 54 }