题解
2024-08-05 08:20:45
发布于:上海
17阅读
0回复
0点赞
像我一样想不到 O(1) 时间复杂度方法的,或者那样做错的,直接广搜即可。
#include<iostream>
#include<queue>
using namespace std;
struct node{
int x,y;
};
queue<node>q;
bool vis[500][500];
int dir[4][2]={2,2,2,-2,-2,2,-2,-2};//这里根据象的走法写出方向数组
int n,a,b,c,d;
int main(){
cin>>n>>a>>b>>c>>d;
a--,b--,c--,d--;
q.push({a,b});
vis[a][b]=1;
while(q.size()){//基本是搜索了所有可以走的地方
node f=q.front();
q.pop();
if(f.x==c&&f.y==d){
cout<<"YES";
return 0;//碰到两人,直接cout<<"YES"并结束程序
}
for(int i=0;i<4;i++){
int nx=f.x+dir[i][0],ny=f.y+dir[i][1];
if(nx>=0&&nx<n&&ny>=0&&ny<n&&!vis[nx][ny]){//判断是否在棋盘上且未到达过
q.push({nx,ny});
vis[nx][ny]=1;
}
}
}
cout<<"NO";//搜不到说明两人不在象的落脚点上,cout<<"NO"即可
return 0;
}
这里空空如也
有帮助,赞一个