描述
在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中，方便查找
代码
#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 ;
}