过了样例但是全部wa
  • 板块P3395 路障
  • 楼主RY111
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/14 21:16
  • 上次更新2024/8/15 08:24:17
查看原帖
过了样例但是全部wa
1233392
RY111楼主2024/8/14 21:16
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n;
const int maxn=1010;
int dx[]= {0,0,1,-1};
int dy[]= {1,-1,0,0};
typedef pair<int,int> pii;
int st[maxn][maxn];
int t[maxn][maxn];
bool flag=0;
void bfs()
{flag=0;
	queue<pii> q;
	q.push({1,1});
	st[1][1]=0;
	while(!q.empty())
	{
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		for(int i=0; i<4; i++)
		{
			int a=x+dx[i];
			int b=y+dy[i];	
			if(a<=0||b<=0||a>n||b>n)
				continue;
				if(st[a][b]!=-1)
				continue;	
			st[a][b]=st[x][y]+1;
			if(st[a][b]>t[a][b])
				continue;
	
			if(a==n&&b==n)
				{
				flag=1;
				return;
				}
			
		
			q.push({a,b});

		}
	}
	return ;


}
void solve()
{
	memset(st,-1,sizeof st);
	memset(t,0x3f,sizeof t);
	cin>>n;
	for(int i=1; i<=2*n-2; i++)
	{
		int x,y;
		cin>>x>>y;
		t[x][y]=i+1;
	}
	bfs();
	if(flag==1)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--)solve();

}

2024/8/14 21:16
加载中...