60pts求助
  • 板块P3395 路障
  • 楼主CurryNo_1
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/9/22 00:45
  • 上次更新2023/11/2 18:48:00
查看原帖
60pts求助
828573
CurryNo_1楼主2023/9/22 00:45
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=1e3+10;
int k,n,x[N],y[N],t;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
bool vis[N][N];
struct node{
	int x;
	int y;
	int t;
};
//第i秒产生的障碍物坐标为(x[i],y[i]) 
void solve()
{
	queue<node>q;
	q.push({1,1,0});//起点坐标
	memset(vis,false,sizeof(vis));
	vis[1][1]=true;
	t=0;
	while(!q.empty())
	{
		node tmp=q.front();
		q.pop();
		int xx,yy,tt;
		tt=tmp.t;
		xx=tmp.x;
		yy=tmp.y;
		if(xx==n && yy==n)//走到终点 
		{
			cout << "Yes" << endl;
			return;
		}
		if(tt!=t && t<=2*n-2)//上一秒已经结束,产生新的障碍物,超过2*n-2秒后不再产生新的障碍物 
		{
			vis[x[t]][y[t]]=true;//产生障碍物 
			t=tt;//更改时间 
		}	
		for(int i=0;i<4;i++)
	    {
	    	int tmpx,tmpy,tmpt;
	    	tmpx=xx+dx[i];
	    	tmpy=yy+dy[i];
	    	tmpt=tt+1;
	    	if(!vis[tmpx][tmpy] && tmpx>0 && tmpy>0 && tmpx<=n && tmpy<=n)
	    	{
	    		vis[tmpx][tmpy]=true;
	    		q.push({tmpx,tmpy,tmpt});
			}
		}
	}
	cout << "No" << endl;
	return;
}
int main()
{
	cin >> k;
	while(k--)
	{
		cin >> n;
		for(int i=1;i<=2*n-2;i++)  cin >> x[i] >> y[i];
		solve(); 
	}
	return 0;
}
2023/9/22 00:45
加载中...