AT_abc193_f [ABC193F] Zebraness

题目描述

有一个纵向 $N$ 行、横向 $N$ 列的网格。
我们用 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。格子 $(i, j)$ 的颜色信息由字符 $c_{i,j}$ 给出。
B 表示该格子被涂成黑色，W 表示该格子被涂成白色，? 表示该格子尚未被涂色。

高桥君可以将尚未涂色的格子分别涂成黑色或白色，从而得到一个黑白相间的网格。
我们定义网格的斑马度为：满足有相同边的两个异色格子的数量之和。如 $(1,1)$ 和 $(1,2)$ 是满足有相同边的（$N \ge 2$）而 $(1,1)$ 和 $(2,2)$ 而不是。注意，如果 $(1,1)$ 和 $(1,2)$ 满足条件，则不应该重复计数 $(1,2)$ 和 $(1,1)$。换言之，一对异色格子只能计算 $1$ 次。

请你求出高桥君能够达到的斑马度的最大值。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2
BB
BW

输出 #1

2

输入输出样例 #2

输入 #2

3
BBB
BBB
W?W

输出 #2

4

输入输出样例 #3

输入 #3

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

输出 #3

40

说明/提示

限制条件

• $1 \leq N \leq 100$
• $c_{i,j}$ 仅为 B、W 或 ? 之一

样例解释 1

通过边相邻的黑格和白格的组合有：格子 $(1,2)$ 与格子 $(2,2)$，格子 $(2,1)$ 与格子 $(2,2)$，共 $2$ 组，因此斑马度为 $2$。

样例解释 2

将格子 $(3,2)$ 涂成白色时，斑马度为 $3$；涂成黑色时，斑马度为 $4$。

由 ChatGPT 4.1 翻译