AT_aising2019_c Alternating Path

[problemUrl]: https://atcoder.jp/contests/aising2019/tasks/aising2019_c $ 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 $ 文字目は `#` となっており、白く塗られているとき文字列 $ S_i $ の $ j $ 文字目は `.` となっています。 黒く塗られたマス $ c_1 $ と白く塗られたマス $ c_2 $ の組であって、以下の条件を満たすものの個数を求めてください。 - 上下左右に隣り合うマスへの移動を繰り返してマス $ c_1 $ からマス $ c_2 $ へ行く方法であって、通るマスの色が黒、白、黒、白・・・と交互になっているものが存在する。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_1 $ $ S_2 $ $ : $ $ S_H $

答えを出力せよ。

### 制約 - $ 1\ \leq\ H,\ W\ \leq\ 400 $ - $ |S_i|\ =\ W $ ($ 1\ \leq\ i\ \leq\ H $) - 各 $ i $ ($ 1\ \leq\ i\ \leq\ H $) に対して、文字列 $ S_i $ は文字 `#` と文字 `.` だけからなる。 ### Sample Explanation 1 上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ と書くとき、条件を満たすマスの組として $ ((1,\ 2),\ (3,\ 3)) $ や $ ((3,\ 1),\ (3,\ 2)) $ などがあります。