求助,4,5点TLE
  • 板块P3395 路障
  • 楼主entity
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/5/21 15:53
  • 上次更新2023/11/4 23:00:11
查看原帖
求助,4,5点TLE
225964
entity楼主2021/5/21 15:53
#include<iostream>
using namespace std;
/*
3

1

2
1 1
1 2

3
3 3
1 1
2 2
2 3

Yes
Yes
No
*/ 
int nn[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct NODE{
	int x,y,t;
}queue[10000001]={};
int T,n;
bool vis[1001][1001]={};
int ink[2001][2]={{0,0}};
void bfs(){
	int f=0,r=1;
	queue[f].x=1;
	queue[f].y=1;
	vis[1][1]=1;
	queue[f].t=0;
	if(2*n-2<=0){
		cout<<"Yes"<<endl;
		return ;
	} 
	while(f<r){
		int x=queue[f].x;
		int y=queue[f].y;
		int t=queue[f].t;
		for(int i=0;i<4;i++){
			int nx=x+nn[i][0];
			int ny=y+nn[i][1];
			if(vis[nx][ny]||x<=0||x>n||y<=0||y>n) continue;
			queue[r].x=nx;
			queue[r].y=ny;
			queue[r].t=t+1;
			vis[nx][ny]=1; 
			r++;
			if(nx==n&&ny==n){
				cout<<"Yes"<<endl;
				return ;
			}
		}
		vis[ink[t][0]][ink[t][1]]=1;
		f++;
	}
	cout<<"No"<<endl;
	return ;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				vis[i][j]=0;
		for(int i=1;i<=2*n-2;i++)
			cin>>ink[i][0]>>ink[i][1];
		bfs();
	}
	return 0;
}
2021/5/21 15:53
加载中...