配点 : $600$ 点

問題文

縦 $N$ マス、横 $N$ マスのマス目があります。 上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と表すことにします。 マス $(i, j)$ の色の情報が文字 $c_{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$ 組あるので、しまうま度は $2$ です。

3
BBB
BBB
W?W

4

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

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

40