只得20求救
  • 板块P3395 路障
  • 楼主Z2011X3Y29
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/25 21:12
  • 上次更新2024/8/26 08:20:58
查看原帖
只得20求救
927015
Z2011X3Y29楼主2024/8/25 21:12
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int t,n,x,y,a[N][N];
bool flag;
struct Node
{
	int x,y,step;
}q[1000*1000+10];
int vis[N][N];
const int mx[] = {0,1,0,-1,0};
const int my[] = {0,0,1,0,-1};
int head,tail;
void bfs (int x,int y)
{
	head = 1,tail = 1;
	q[tail].x = x;
	q[tail].y = y;
	q[tail].step = 0;
	tail++;
	vis[1][1] = 1;
	while (head < tail)
	{
		for (int i = 1; i <= 4; i++)
		{
			int dx = q[head].x + mx[i];
			int dy = q[head].y + my[i];
			if (dx >= 1 && dx <= n && dy >= 1 && dy <= n && vis[dx][dy] == 0)
			{
				if (q[head].step + 1 <= a[dx][dy])
				{
					vis[dx][dy] = 1;
					q[tail].step = q[head].step + 1;
					q[tail].x = dx;
					q[tail].y = dy;
					tail++;
					if (dx == n && dy == n)
					{
						flag = true;
						break;
					}
				}
			}
		}
		head++;
		if (flag) 
		{
			break;
		}
	}
}
int main(void)
{
	cin >> t;
	while(t--)
	{
		flag = false;
		cin >> n;
		if (n == 1)
		{
			cout << "Yes" << endl;
			continue;
		}
		memset(a,0x3f,sizeof(a));
		memset(vis,0,sizeof(vis));
		for (int i = 1; i <= 2*n-2; i++)
		{
			cin >> x >> y;
			a[x][y] = i;
		}
		bfs(1,1);
		if (flag)
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No";
		}
	}
	return 0;
} 
2024/8/25 21:12
加载中...