斑马度

题目描述

有一个纵向 $N$ 格、横向 $N$ 格的方格盘。

将从上数第 $i$ 行、从左数第 $j$ 列的格子记作格子 $(i, j)$。 格子 $(i, j)$ 的颜色信息由字符 $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$ 组,因此斑马度为 $2$。

3
BBB
BBB
W?W

4

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

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

40

数据范围

• $1 \le N \le 100$
• $c_{i, j}$ 是 B, W, ? 中的某一个