/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 N マス、横 N マスのマス目があります。
上から i 行目、左から j 列目のマスをマス (i, j) と表すことにします。
マス (i, j) の色の情報が文字 c_{i,j} により与えられます。
B はマスが黒で塗られていることを、
W はマスが白で塗られていることを、
? はマスにまだ色が塗られていないことを表します。
高橋くんは、まだ色が塗られていないマスをそれぞれ黒または白で塗り、白黒のマス目を作ります。
マス目の しまうま度 を、辺で接する黒マスと白マスの組の個数と定義します。
高橋くんが達成できるしまうま度の最大値を求めてください。
制約
- 1 ≤ N ≤ 100
- c_{i, j} は
B,W,?のいずれか
入力
入力は以下の形式で標準入力から与えられる。
N
c_{1,1} \dots c_{1,N}
\hspace{20pt}\vdots
c_{N,1} \dots c_{N,N}
出力
答えを出力せよ。
入力例 1
2 BB BW
出力例 1
2
辺で接する黒マスと白マスの組は、マス (1, 2) とマス (2, 2) 、マス (2, 1) とマス (2, 2) の 2 組あるので、しまうま度は 2 です。
入力例 2
3 BBB BBB W?W
出力例 2
4
マス (3, 2) を白で塗ったときのしまうま度は 3 、黒で塗ったときのしまうま度は 4 です。
入力例 3
5 ????? ????? ????? ????? ?????
出力例 3
40
Score : 600 points
Problem Statement
We have a grid with N horizontal rows and N vertical columns.
Let (i, j) denote the square at the i-th row from the top and j-th column from the left. A character c_{i,j} describes the color of (i, j).
B means the square is painted black; W means the square is painted white; ? means the square is not yet painted.
Takahashi will complete the black-and-white grid by painting each unpainted square black or white.
Let the zebraness of the grid be the number of pairs of a black square and a white square sharing a side.
Find the maximum possible zebraness of the grid that Takahashi can achieve.
Constraints
- 1 ≤ N ≤ 100
- c_{i, j} is
B,W, or?.
Input
Input is given from Standard Input in the following format:
N
c_{1,1} \dots c_{1,N}
\hspace{20pt}\vdots
c_{N,1} \dots c_{N,N}
Output
Print the answer.
Sample Input 1
2 BB BW
Sample Output 1
2
We have two pairs of a black square and a white square sharing a side: (1, 2), (2, 2) and (2, 1), (2, 2), so the zebraness of this grid is 2.
Sample Input 2
3 BBB BBB W?W
Sample Output 2
4
Painting (3, 2) white makes the zebraness 3, and painting it black makes the zebraness 4.
Sample Input 3
5 ????? ????? ????? ????? ?????
Sample Output 3
40