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
*/