AT_abc413_g 题解
这应该是近期最水的 G 了。
题目就是给定一张巨大的网格，上面有一些障碍物，问可否通过上下左右移动（不可经过障碍物）从左上角走到右下角。
第一反应肯定是直接暴力 BFS 啥的对吧，但是会超时没错吧。
因为我们的空白格子太多了导致超时。但是障碍物少得可怜啊！所以想到反过来。
考虑一下，什么情况才会无法走通呢？当然是有一堆障碍物连成一条歪歪扭扭的线，把左上角与右下角分隔开了。
在草稿纸上多画几张图就能知道，其实上就是需要第一行或者最后一列的某个障碍物，能够通过八个方向（上下左右，以及左上、左下、右上、右下）的移动到达第一列或者最后一行。
这不就结束了吗？跑一个常规 BFS，先把第一行和最后一列的所有障碍物全部压进去，跑的过程中看看有没有第一列或者最后一行的就行了。注意跑 BFS 的时候只能跑障碍物哦。
来，上代码：
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;};
map<pair<int,int>,bool> mp;
int n,m,k;bool flag;queue<node> q;
int dx[]={1,1,1,-1,-1,-1,0,0},dy[]={-1,0,1,-1,0,1,-1,1};
int main(){
cin>>n>>m>>k;
for(int i=1;i<=k;i++){
int x,y;cin>>x>>y;mp[{x,y}]=1;
if(x==1||y==m)q.push({x,y}),mp[{x,y}]=0;
}
while(!q.empty()){
auto [x,y]=q.front();q.pop();
if(x==n||y==1){flag=1;break;}
for(int o=0;o<8;o++){
int x2=x+dx[o],y2=y+dy[o];
if(x2<1||x2>n||y2<1||y2>m)continue;
if(mp[{x2,y2}]!=1)continue;
mp[{x2,y2}]=0,q.push({x2,y2});
}
}
if(flag)cout<<"No\n";else cout<<"Yes\n";
return 0;
}