← 返回题目列表

AtCoder · abc193_f

F. 斑马

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个网格 N 水平行和 N 垂直列。
让 (i, j) 表示位于 i从顶部数第行和 j左起第 列。一个角色 c_{i,j} 描述了颜色 (i, j).
B 表示方块被涂成黑色; W 表示方块被涂成白色; ? 表示该正方形尚未绘制。

高桥将通过将每个未绘制的正方形涂成黑色或白色来完成黑白网格。
让 斑马 网格的 是共享一条边的黑色方块和白色方块对的数量。
找出 Takahashi 可以实现的网格的最大可能斑马度。

约束

  • 1 ≤ N ≤ 100
  • c_{i, j} is 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

3
BBB
BBB
W?W

示例输出 2

4

绘画 (3, 2) 白色打造斑马气质 3,将其涂成黑色会产生斑马纹 4.


示例输入 3

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

示例输出 3

40