题解：P11808 [PA 2017] 摆砖 / Carcassonne
D2T1
·
·
题解
不太像题。
关键想法是枚举新增的 k 个点距离最近 \texttt{\#} 点的曼哈顿距离（设为 dis_{i,j}）。
k=1。
任意一个 dis=1 的点都可以。
k=2。
两种情况：两个 dis=1 的点，一个 dis=1 的点和与之相邻的一个 dis=2 的点。
k=3。
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$ 集合是否合法即可。