F - 斑马状

得分：$600$ 分

问题描述

我们有一个 $N \times N$ 的网格。
用 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的方格。一个字符 $c_{i,j}$ 表示 $(i, j)$ 的颜色。
B 表示该方格涂黑；W 表示该方格涂白；? 表示该方格尚未涂色。

高桥将完成整个黑白网格，其会给每个尚未涂色的方格涂上黑色或白色。
斑马状被定义为拥有一对共边的黑色方格和白色方格的个数。
找出高桥能够实现的网格的最大斑马状。

约束

• $1 \leq N \leq 100$
• $c_{i, j}$ 是 B、W 或者 ?。

输入

从标准输入中按下列格式输入：

$N$

$c_{1,1} \dots c_{1,N}$

$\hspace{20pt}\vdots$

$c_{N,1} \dots c_{N,N}$

输出

输出答案。

2
BB
BW

2

有两对共边的黑色方格和白色方格：$(1, 2), (2, 2)$ 和 $(2, 1), (2, 2)$，所以这个网格的斑马状为 $2$。

3
BBB
BBB
W?W

4

将 $(3, 2)$ 涂白色使得斑马状为 $3$，将其涂黑色使得斑马状为 $4$。

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

40