2755: 国际象棋
时间限制(普通/Java):10000MS/30000MS 内存限制:65536KByte
描述
在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!
题目来源
题目链接：http://tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=2755
棋盘的大小为1000000*1000000的，显然我们不能开这么大的数组，所以需要离散化一下，把需要的点存下了，而没有走到的点就不需要存储了。
#include<cstdio>
#include<map>
#include<cmath>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
struct zuobiao
{
pair<int,int>w;//能走到的点
int t;//走到这个点要的步数
}q,s;
queue<zuobiao>que;
int dir[8][2] = {1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2};
int n,m;
map<pair<int,int>,int>v;//判断点是否走到
int bfs()
{
int i,tmp;
if(abs(s.w.first-q.w.first)/2>m||abs(s.w.second-q.w.second)/2>m)return 0;//剪枝去掉走不到的情况
v.clear();
v[s.w]=0;
que.push(s);
while(!que.empty())
{
s=que.front();
que.pop();
tmp=v[s.w];
if(tmp>=m)break;
for(i=0;i<8;i++)
{
zuobiao t;
t.w.first=s.w.first+dir[i][0];
t.w.second=s.w.second+dir[i][1];
if(t.w==q.w)
return 1;
if(t.w.first>=1&&t.w.second>=1&&t.w.second<=n&&t.w.first<=n&&v.find(t.w)==v.end())
{
t.t=tmp+1;
v[t.w]=t.t;
que.push(t);
}
}
}
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
while(!que.empty())que.pop();
scanf("%d%d%d%d",&s.w.first,&s.w.second,&q.w.first,&q.w.second);
if(bfs())
printf("Knight can reach Queen within %d moves!
",m);
else
printf("Knight cannot reach Queen within %d moves!
",m);
}
}