AT_aising2019_c.Alternating Path

有一个 $H$ 行 $W$ 列的网格，每个格子被涂成黑色或白色。

给定 $H$ 个长度为 $W$ 的字符串 $S_1,\ S_2,\ ...,\ S_H$，用于表示每个格子的颜色。对于从上到下第 $i$ 行、从左到右第 $j$ 列的格子（$1 \leq i \leq H,\ 1 \leq j \leq W$），如果该格子被涂成黑色，则字符串 $S_i$ 的第 $j$ 个字符为 #，如果被涂成白色，则为 .。

请计算满足以下条件的黑色格子 $c_1$ 和白色格子 $c_2$ 的有序对的数量：

• 存在一种从格子 $c_1$ 移动到格子 $c_2$ 的方式，每次只能移动到上下左右相邻的格子，且经过的格子的颜色依次为黑、白、黑、白……，即颜色交替。

输入按以下格式从标准输入给出。

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出答案。

限制条件

• $1 \leq H, W \leq 400$
• $|S_i| = W$（$1 \leq i \leq H$）
• 对于每个 $i$（$1 \leq i \leq H$），字符串 $S_i$ 仅由字符 # 和 . 组成。

样例解释 1

记从上到下第 $i$ 行、从左到右第 $j$ 列的格子为 $(i, j)$，则满足条件的格子对有 $((1, 2), (3, 3))$、$((3, 1), (3, 2))$ 等。

由 ChatGPT 4.1 翻译