← 返回题目列表

AtCoder · aising2019_c

C. 备用路径

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

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