传送门:http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2755
思路:对起点到终点进行广搜,由于n特别大,不能用二维数组记录走过的点,可以用STL的map进行记录,map<pair<int,int>,int> v; 如果出现的点可以进行v[point] = 1;
另外可以剪枝 if(abs(sx-ex)/2>m||abs(sy-ey)/2>m)return 0; 其中sx,sy代表起点的横纵坐标,ex,ey代表终点的横纵坐标
AC代码如下:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#define LL long long
#include<assert.h>
using namespace std;
int go[][]={{,},{,-},{-,},{-,-},{,},{,-},{-,},{-,-}};
int n;
map<pair<int,int>,int> v;
struct note{
int x,y,step;
}pos,q;
int check(int x,int y){
if(x < ||x > n || y < || y > n)return ;
return ;
}
int bfs(int sx,int sy,int ex,int ey,int m){
pair<int ,int> a;
a.first = sx;a.second = sy;
v[a] = ;
if(abs(sx-ex)/>m||abs(sy-ey)/>m)return ;//剪枝
queue<note>que;
while(!que.empty()) que.pop(); pos.x = sx;pos.y = sy;pos.step = ;
que.push(pos);
while(que.size()){
q = que.front();
que.pop();
if(q.step > m)return ;
if(q.x == ex && q.y == ey && q.step <= m) return ;
for(int i = ; i < ; i ++){
int dx = q.x + go[i][];
int dy = q.y + go[i][];
pair<int,int>b;
b.first = dx;b.second = dy;
if(check(dx,dy) && q.step < m && v[b] == ){
pos.step = q.step + ;
pos.x = dx;pos.y = dy;
v[b] = ;
if(dx == ex && dy == ey && pos.step <= m) return ;
que.push(pos);
}
}
}
return ;
}
int main(){
int m;
while(~scanf("%d %d",&n,&m)){
v.clear();
int sx,sy,ex,ey;
scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
if(!bfs(sx,sy,ex,ey,m)){
printf("Knight cannot reach Queen within %d moves!\n",m);
}
else{
printf("Knight can reach Queen within %d moves!\n",m);
} }
}