【0】题解：AT_abc413_g [ABC413G] Big Banned Grid【搜索】

· · 题解

有史以来最简单的 G 题。

题意：给你一个 H\times M 的地图，然后给你 K 个障碍物，问左上是否能走到右下。

首先直接走会超时，因为地图大小是 H\times M\leq 10^{10}。我们考虑转化这个问题，判断是否有一条墙壁完整挡住了地图。这时我们就需要分一下类：

然后我们考虑如何找这样的墙壁。可以考虑用 set 记录，枚举一下墙壁的起点，然后暴力搜。注意这里要用八连通的搜法，原因可以看样例的墙壁。并且，每搜一个点，就要删掉 set 内的记录，表示已经存在了。当墙壁闭合，也就是框住了起点，问题也就有答案了。

具体看代码：

#include<bits/stdc++.h>
using namespace std;
int h,m,k;
int dx[]={0,1,0,-1,1,1,-1,-1},
    dy[]={1,0,-1,0,-1,1,-1,1};
set<pair<int,int>>Node;
void dfs(int x,int y){
    Node.erase({x,y}); // use
    if(x==h||y==1){
        // webbed.
        cout<<"No\n";
        exit(0);
    }
    for(int i=0;i<8;i++){
        int nx=x+dx[i],
            ny=y+dy[i];
        if(nx<1||ny<1||nx>h||ny>m)
            continue;
        if(!Node.count({nx,ny}))
            continue;
        dfs(nx,ny);
    }
}
signed main(){
    cin>>h>>m>>k;
    for(int i=1;i<=k;i++){
        int x,y;
        cin>>x>>y;
        Node.insert({x,y});
    }
    for(int i=1;i<=m;i++)
        if(Node.count({1,i}))dfs(1,i);
    for(int i=1;i<=h;i++)
        if(Node.count({i,m}))dfs(i,m);
    cout<<"Yes";    
    return 0;
}