题目描述

縦 $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}$

输出格式

答えを出力せよ。

题目大意

给你一个 $n\times n$ 的黑白矩阵，格子 $(i,j)$ 可能是白的(W)，黑的(B)，不确定(?)。现在让你确定每个不确定格子的黑白，使得两边颜色不一样的边数最大，输出这个最大值。（这里的边指的是每个格子的边）

2
BB
BW

2

3
BBB
BBB
W?W

4

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

40

提示

制約

• $1\ <\ = N\ <\ =\ 100$
• $c_{i,\ j}$ は B, W, ? のいずれか

Sample Explanation 1

辺で接する黒マスと白マスの組は、マス $(1,\ 2)$ とマス $(2,\ 2)$ 、マス $(2,\ 1)$ とマス $(2,\ 2)$ の $2$ 組あるので、しまうま度は $2$ です。

Sample Explanation 2

マス $(3,\ 2)$ を白で塗ったときのしまうま度は $3$ 、黒で塗ったときのしまうま度は $4$ です。