题解 | #「Nhk R1 A」Initiale Dorimu#

C 题有问题呀

出个hack数据

4 4
8
3 4
3 3
3 2
3 1
1 0
1 1
1 2
1 3

他说只能向上向右， 但是这个数据需要向上向右向下向右向上才能到达 但是ac的代码出Yes

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int > PII;

const int N = 1e5;

int n, m, k;
map<PII , bool > mp, st;

struct Node
{
	int x, y;
	bool operator < (const Node & t) const{
		return x < t.x;
	}
}p[N], q[N];

bool bfs(int pos)
{
	int tt = -1, hh = 0;
	q[++ tt] = p[pos];
	
	while(tt >= hh)
	{
		auto t = q[hh ++];
		int nx = t.x, ny = t.y;
		st[{nx, ny}] = true;
		if(ny == 0 || nx == m)
		{
			return true;
		}
		
		if(mp[{nx+1, ny+1}] && !st[{nx+1, ny+1}]) 
			q[++ tt] = {nx+1, ny+1};
		if(mp[{nx+1, ny}] && !st[{nx+1, ny}]) 
			q[++ tt] = {nx+1, ny};
		if(mp[{nx+1, ny-1}] && !st[{nx+1, ny-1}]) 
			q[++ tt] = {nx+1, ny-1};
		if(mp[{nx, ny+1}] && !st[{nx, ny+1}]) 
			q[++ tt] = {nx, ny+1};
		if(mp[{nx, ny-1}] && !st[{nx, ny-1}]) 
			q[++ tt] = {nx, ny-1};
		if(mp[{nx-1, ny+1}] && !st[{nx-1, ny+1}])
			q[++ tt] = {nx-1, ny+1};
		if(mp[{nx-1, ny}] && !st[{nx-1, ny}])
			q[++ tt] = {nx-1, ny};
		if(mp[{nx-1, ny-1}] && !st[{nx-1, ny-1}])
			q[++ tt] = {nx-1, ny-1};
	}
	return false;
}

int main()
{
	cin >> n >> m >> k;
	for(int i = 1; i <= k; i ++)
	{
		cin >> p[i].x >> p[i].y;
		mp[{p[i].x, p[i].y}] = true;
	}
	
	sort(p+1, p+1+k);
	
	bool is = false;
	for(int i = 1; i <= k; i ++)
	{
		if(!st[{p[i].x, p[i].y}] && (p[i].x == 0 || p[i].y == n) && bfs(i))
		{
			is = true; // 表示可以封死
			break;
		}
	}
	if(!is) puts("Yes");
	else puts("No");
	return 0;
}
/*
4 4
4
2 0
2 1
2 2
2 3

*/