题解：AT_abc413_g [ABC413G] Big Banned Grid

· · 题解

思路

题意即为我们需要找到是否存在一大块（八）连通的障碍，把高桥和终点隔开。

能够发现，一块连通的障碍把高桥和终点隔开，就是它触及左侧边界或下侧边界，且触及右侧边界或上侧边界。于是考虑维护一个表示连通的障碍的并查集，并记录每个并查集最上/下/左/右的障碍的位置。

如何合并所有相邻的并查集？我们可以考虑用一个 map 去存储坐标和障碍编号的关系，对于每一个障碍检测它周围的八个格子，如果格子中有另外一个障碍就把它们所在的并查集合并。时间复杂度 O(K\alpha(K))。

参考代码仅运用路径压缩，理论上复杂度为 O(K\log K)。

代码

#include<bits/stdc++.h>
#define gc getchar
using namespace std;
const int N = 300000,d[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int h,w,k,r[N],c[N],f[N],lm[N],rm[N],um[N],dm[N];
map<pair<int,int>,int>m;
bool fal;
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> h >> w >> k;
  for(int i = 1;i <= k;i ++){
    cin >> r[i] >> c[i];
    f[i] = i,lm[i] = rm[i] = c[i],um[i] = dm[i] = r[i];//维护并查集四个方向的最远位置
    m[{r[i],c[i]}] = i;
  }
  for(int i = 1;i <= k;i ++){
    int x = r[i],y = c[i];
    for(int j = 0;j < 8;j ++){//检测每一个障碍周围的八个格子并合并
      int dx = x + d[j][0],dy = y + d[j][1];
      if(m[{dx,dy}]){
        int u = find(i),v = find(m[{dx,dy}]);
        lm[v] = min(lm[v],lm[u]),um[v] = min(um[v],um[u]);
        rm[v] = max(rm[v],rm[u]),dm[v] = max(dm[v],dm[u]);
        f[u] = v;
      }
    }
  }
  for(int i = 1;i <= k;i ++) //如果有一个障碍连通块横贯左下到右上，那么高桥将不能到达终点
    if((lm[i] == 1 || dm[i] == h) && (rm[i] == w || um[i] == 1)) fal = true;
  if(fal) printf("No\n");
  else printf("Yes\n");
  return 0;
}