Contest Duration: - (local time) (100 minutes) Back to Home
F - Zebraness /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N マス、横 N マスのマス目があります。

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}

2
BB
BW

2

3
BBB
BBB
W?W

### 出力例 2

4

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

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}

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.

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.

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

40