描述
在nn的国际象棋棋盘中，给定一“马(Knight)”和一“后(Queen)”的位置，问“马”能否在m步之内（包括m步）到达“后”的位置？马的走法是：每步棋先横走或直走一格，然后再斜走一格，即走“日”字，没有“中国象棋”中“蹩马腿”的限制。比如在88的棋盘中，马的位置为(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!
解题思路
看到题目发现就是用BFS，但是棋盘比较大，直接开二维数组一定会超内存。所以我用了map只标记要走的格子而不是每个格子都先标记。还有我们可以判断abs(ma.x-qx)>m2和abs(ma.y-qy)>m2有一个成立时就不会在m布内到达皇后的位置。
代码
#include <bits/stdc++.h>
using namespace std;
map<pair<int ,int >,int> map1;//使用map来标记马已经走过的位置
int qx,qy;
int dir[8][2] = {
{
1,-2}, {
2,-1}, {
2,1}, {
1,2},{
-1,2}, {
-2,1}, {
-2,-1}, {
-1,-2}};//马能走的位置
int n,m;struct node
{
int x,y,step;
};
node ma;
queue<node>que;
int check(node tt)
{
return tt.x>=1&&tt.x<=n&&tt.y>=1&&tt.y<=n;//判断下个点在不在范围内
}
int bfs()
{
node s,t;pair<int ,int > a;if(abs(ma.x-qx)>m*2||abs(ma.y-qy)>m*2)return 0; //修枝if(m<=0) return 0;while(!que.empty()){
s=que.front();que.pop();//队首出队for(int i=0;i<8;i++){
t.x=s.x+dir[i][0];t.y=s.y+dir[i][1];a.first=t.x;a.second=t.y;if(check(t)&&map1.find(a)==map1.end())//判断马有没有走过这个点{
map1[a]=1;//将走过的位置标记为1t.step=s.step+1;//步数+1if(t.x==qx&&t.y==qy&&t.step<=m){
return 1;//当马在m步内到达皇后位置时返回1}que.push(t);}}}return 0;
}
int main()
{
while(~scanf("%d %d",&n,&m)){
while(!que.empty())que.pop();map1.clear();scanf("%d %d",&ma.x,&ma.y);ma.step=0;que.push(ma);//将初始马的位置入队scanf("%d %d",&qx,&qy);int t=bfs();if(t)printf("Knight can reach Queen within %d moves!\n",m);else printf("Knight cannot reach Queen within %d moves!\n",m);}return 0;
}