AT_abc413_g [ABC413G] Big Banned Grid

· · 题解

前言

学考 Day 1 的晚上发现有 ABC，来看一下题目。

前面的题目不想做。

感觉没有以往 G 的难度。 ## 正文 若一个障碍位于另一个障碍周围的 $8$ 个格子中，则称这两个障碍相连。 若障碍 $p$ 与 $q$ 相连，$q$ 与 $r$ 相连，则称 $p$ 与 $r$ 相连。 令集合 $S_1$ 为所有位于上边界（横坐标 $x = 1$）或右边界（纵坐标 $y = W$）的障碍，$S_2$ 为所有位于下边界（横坐标 $x = H$）或左边界（纵坐标 $y = 1$）的障碍。 显然，若 $\exists i \in S_1, j \in S_2$，满足 $i$ 与 $j$ 相连，则起点到终点无路径。 将所有障碍按横坐标排序后，将能连接的障碍相连。连接时只需考虑横坐标之差 $\leq 1$ 的障碍。 考虑并查集。 开始前先将所有 $S_1$ 中的障碍与虚点 $k+1$ 相连，将所有 $S_2$ 中的障碍与虚点 $k+2$ 相连。最后判断 $k+1$ 与 $k+2$ 是否相连即可。 注意特判 $H = 1$ 或 $W = 1$ 的情况。 [Submission](https://atcoder.jp/contests/abc413/submissions/67357542)。