萌新求助!
  • 板块P3395 路障
  • 楼主Yee_Aries
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/7/24 12:10
  • 上次更新2023/11/4 13:28:28
查看原帖
萌新求助!
151481
Yee_Aries楼主2021/7/24 12:10
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,a,k,dis[105][105];
int dx[4]={1,-1,0,0},
    dy[4]={0,0,1,-1};
typedef pair<int ,int > P;
void bfs()
{
	int x[105]={0},y[105]={0},t=0;
	queue<P> q;
	memset(dis,INF,sizeof(dis));
	dis[1][1]=0;
	q.push(P(1,1));
	for(int j=1;j<=2*a-2;j++)
	   cin>>x[j]>>y[j];
	while(!q.empty())
	{
		t++;
		P tmp=q.front();
		q.pop();
		if(tmp.first==n&&tmp.second==n)
		{
			k=1;
			break;
		}
		for(int i=0;i<4;i++)
		{
			int tx=tmp.first+dx[i],
				ty=tmp.second+dy[i];
			if(tx>=0&&tx<n&&ty>=0&&ty<n&&dis[tx][ty]==INF)
			{
				dis[tx][ty]=0;
				q.push(make_pair(tx,ty));			
			}
		}
		if(t<=2*a-2)
		  dis[x[t]][y[t]]=0;
	}
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		bfs();
		if(k)
	  	  cout<<"Yes"<<endl;
		else
	  	  cout<<"No"<<endl;
	}
	return 0;
}

测试点1WA 测试点2-4RE

2021/7/24 12:10
加载中...