80分求助 WA#1
  • 板块P3395 路障
  • 楼主lcbridgeAK CSP-S
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/1/31 11:44
  • 上次更新2023/10/24 02:25:17
查看原帖
80分求助 WA#1
546681
lcbridgeAK CSP-S楼主2023/1/31 11:44

RT,求助各位大佬,谢谢

#include <bits/stdc++.h>
using namespace std;
int n,f;
struct pos{
	int x,y,k;
};
int walk[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool vis[1005][1005];  
int c[1005][1005];
bool check(int x,int y){
	if(x<1||x>n||y<1||y>n)return false;
	return true;
}
void bfs(){
	queue <pos> q;           
	q.push({1,1,0});
	while(!q.empty()){
		pos now=q.front();
		q.pop();
		int nx=now.x,ny=now.y,nk=now.k;
		if(nx==n&&ny==n){
			f=1;
			break;
		}
		if(!check(nx,ny)||vis[nx][ny]||(nk>=c[nx][ny]&&c[nx][ny]!=0))continue;
		vis[nx][ny]=1;
		for(int i=0;i<5;i++){
			int nnx=nx+walk[i][0];
			int nny=ny+walk[i][1];
			if(check(nnx,nny)&&!vis[nnx][nny])q.push({nnx,nny,nk+1});
		}
	}
	return ;
}
int main(){
	int T,x,y;
	scanf("%d",&T);
	while(T--){
		f=0;
		memset(vis,0,sizeof(vis));
		memset(c,0,sizeof(c));
		scanf("%d",&n);
		for(int i=1;i<=2*n-2;i++){
			scanf("%d%d",&x,&y);
			c[x][y]=i;
		}
		bfs();
		if(f)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
2023/1/31 11:44
加载中...