分数: 300 点
问题陈述
有一个网格 H 行和 W 列,其中每个方块都漆成黑色或白色。
你被给予 H 字符串 S_1, S_2, ..., S_H,每个长度 W。
如果正方形位于 i从顶部开始的第行和 j左起第 1 列被漆成黑色, j- 字符串中的第一个字符 S_i is #;如果那个正方形被漆成白色, j- 字符串中的第一个字符 S_i is ..
求黑色方块的对数 c_1 和一个白色方块 c_2 满足以下条件:
- 从广场有一条路 c_1 到广场 c_2 我们通过交替的黑白方块序列重复移动到垂直或水平相邻的方块:黑,白,黑,白......
约束
- 1 \leq H, W \leq 400
- |S_i| = W (1 \leq i \leq H)
- 对于每个 i (1 \leq i \leq H),字符串 S_i 由字符组成
#和..
输入
输入由标准输入按以下格式给出:
H W S_1 S_2 : S_H
输出
打印答案。
示例输入 1
3 3 .#. ..# #..
示例输出 1
10
满足条件的一些对是 ((1, 2), (3, 3)) 和 ((3, 1), (3, 2)),其中 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
示例输入 2
2 4 .... ....
示例输出 2
0
示例输入 3
4 3 ### ### ... ###
示例输出 3
6