#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=3000;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int a[N][N],b[N],c[N],st[N][N];
int n,t,k=1;
int bfs(PII start,PII end,int m){
if(start==end) return 1; //如果起点就是终点 返回1
queue <PII> q;
q.push(start); //将起点压入队列中
st[start.x][start.y]=1;
while(q.size()){
PII t=q.front(); //取出队首
q.pop(); //弹出
for(int i=0;i<4;i++){
int tx=t.x+dx[i];
int ty=t.y+dy[i]; //四个方向试探
if(tx<0||tx>n||ty<0||ty>n) continue; //如果越界了 continue
if(st[tx][ty]!=-1) continue; //如果已经走过了 continue
if(a[tx][ty]==1) continue; //如果有障碍 continue
st[tx][ty]=1; //可以走,把可以走的都表记为1
if(make_pair(tx,ty)==end)
return 1; //可以走到终点,返回1
q.push({tx,ty});
}
a[b[k]][c[k]]=1; // 每过一秒,就把障碍添加到地图 a中
k++;
}
}
int main(){
cin>>t;
while(t>0){
t--;
memset(a,0,sizeof a); //地图清零
memset(b,0,sizeof b);
memset(c,0,sizeof c);
memset(st,-1,sizeof st); //状态清零
scanf("%d",&n);
for(int i=1;i<=2*n-2;i++){
scanf("%d %d",&b[i],&c[i]);
}
PII start,end;
start={1,1};
end={n,n};
int res=bfs(start,end);
if(res==1) cout<<"Yes";
else cout<<"No";
}
return 0;
}
你好,我是有问必答小助手。为了技术专家团更好地为您解答问题,烦请您补充下(1)问题背景详情,(2)您想解决的具体问题,(3)问题相关代码图片或者报错信息。便于技术专家团更好地理解问题,并给出解决方案。
您可以点击问题下方的【编辑】,进行补充修改问题。