Zebraness

题目描述

我们有一个由 $N$$行水平行和$N$$ 列垂直列组成的网格。
令 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的方格。方格的颜色由字符 $c_{i,j}$ 描述。
$B$ 表示该方格被涂成黑色；$W$ 表示该方格被涂成白色；$?$ 表示该方格尚未被涂色。 Takahashi 将通过把每个未涂色的方格涂成黑色或白色来完成黑白网格。
令该网格的 zebraness 为一对相邻并共享一条边的黑方格与白方格的计数。
求 Takahashi 能达到的网格的最大可能 zebraness。

输入格式

输入从标准输入按如下格式给出： $N$ $c_{1,1} \dots c_{1,N}$ $\hspace{20pt}\vdots$ $c_{N,1} \dots c_{N,N}$

输出格式

输出答案。

2
BB
BW

2

3
BBB
BBB
W?W

4

5
?????
?????
?????
?????
?????

40

提示

$1 ≤ N ≤ 100$ $c_{i, j}$ 是 $B$、$W$ 或 $?$。我们有两对一黑一白且共享一条边的方格：$(1, 2), (2, 2)$ 和 $(2, 1), (2, 2)$，所以该网格的 zebraness 为 $2$.
将 $(3, 2)$ 涂成白色使 zebraness 变为 $3$，将其涂成黑色使 zebraness 变为 $4$.

标签: AtCoder|abc193F

来源

AtCoder|abc193F