自动搬运

查看原文

来自洛谷，原作者为

	D2T1 没复活就是似了 | 头发绿绿戴个帽帽，脑袋大大，喜欢唱唱

搬运于2025-08-24 23:10:24，当前版本为作者最后更新于2025-05-22 17:56:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不太像题。

关键想法是枚举新增的 $k$ 个点距离最近 $\texttt{\#}$ 点的曼哈顿距离（设为 $dis_{i,j}$）。

$k=1$。

任意一个 $dis=1$ 的点都可以。

$k=2$。

两种情况：两个 $dis=1$ 的点，一个 $dis=1$ 的点和与之相邻的一个 $dis=2$ 的点。

$k=3$。

$dis$ 集合有四种情况：

1. $\{1,1,1\}$：任选三个 $dis=1$ 的点。
2. $\{1,1,2\}$：枚举这个 $dis=2$ 的点，分类讨论那两个 $dis=1$ 是否都与这个点相邻。
3. $\{1,2,2\}$：枚举这个 $dis=1$ 的点，任选两个与之相邻的 $dis=2$ 的点。
4. $\{1,2,3\}$：枚举这个 $dis=2$ 的点，任选与之相邻的一个 $dis=1,dis=3$ 的点。

$k=4$。

$dis$ 集合有八种情况：

1. $\{1,1,1,1\}$：任选四个 $dis=1$ 的点。
2. $\{1,1,1,2\}$：枚举这个 $dis=2$ 的点，分类讨论那三个 $dis=1$ 的点有几个与这个点相邻。
3. $\{1,1,2,2\}$：最难的一种情况。有两种子情况：首先，两个 $2$ 都与选择的 $1$ 有相邻，对于大部分情况，可以选择的 $2$ 集合大小等于两个 $1$ 的 $2$ 邻域大小之和，特例是两个 $1$ 点距离为 $2$，特判一下就可以；其次，存在一个 $2$ 不与选择的那两个 $1$ 相邻，那么枚举另一个 $2$，选择它旁边的一个 $1$ 一个 $2$ 后，计算与前者 $2$ 不相邻的 $1$ 个数即可。
4. $\{1,1,2,3\}$：枚举这个 $dis=2$ 的点，分类讨论那两个 $dis=1$ 是否都与这个点相邻，因为 $dis=3$ 的点一定与它相邻。
5. $\{1,*,*,*\}$： 这里实际上可以列出四种情况，但是它们可以一起处理，因为此时有性质：这四个点一定形成一个四连通块。那么枚举所有 $19$ 种四连块，判断它们的 $dis$ 集合是否合法即可。