分数: 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