AT_past20_j.グリッドの禁止パターン

给定一个 $N \times N$ 的网格，共有 $N$ 行 $N$ 列。$(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。初始时，每个格子被涂成黑色或白色：若 $S_{i, j}$ 为 #，则格子 $(i, j)$ 为黑色；若 $S_{i, j}$ 为 .，则为白色。

你可以多次选择一个格子，并将其涂成黑色，使得整个网格满足以下条件：

• 对于任意一个白色格子 $(x, y)$，其上下左右相邻的格子（即 $(x - 1, y)$、$(x + 1, y)$、$(x, y - 1)$、$(x, y + 1)$，不存在的位置无需考虑）中，最多只有两个被涂成黑色。

至少需要多少次操作才能使网格满足条件？

输入由标准输入给出，格式如下：

$N$
$S_{1,1}S_{1,2}\cdots S_{1,N}$
$S_{2,1}S_{2,2}\cdots S_{2,N}$
$\vdots$
$S_{N,1}S_{N,2}\cdots S_{N,N}$

输出一行，表示满足条件所需的最少操作次数。

样例解释 1

$(2, 2)$ 格子为白色，其上下左右四个相邻格子均为黑色。只需将 $(2,2)$ 涂黑即可使网格满足条件。

样例解释 2

只需将 $(2,2)$ 涂黑即可使网格满足条件。

样例解释 3

只有将所有白色格子都涂成黑色才能使网格满足条件。

约束条件

• $1 \leq N \leq 2000$
• $S_{i, j}$ 仅为 . 或 #。

由 ChatGPT 5 翻译