C - 右折 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

NM 列のマス目があります。上から i 行目、左から j 列目にあるマスを (i,j) で表します。 特に、左上のマスは (1,1) であり、右下のマスは (N,M) です。 マス目の状態は 二次元配列 s で表され、s_{ij}# のときマス (i,j) には障害物があり、. のとき障害物がないことを表します。

高橋君は、このマス目のいずれかのマスに、上下左右いずれかの方向を向けたロボットを置きました。 ロボットは向いている方向に 1 マス以上まっすぐ進んだ後、向きを右に 90 度変え、再びまっすぐに 1 マス以上進んで停止しました。 この過程でロボットが通ったマス(置かれたマスおよび停止したマスを含む)のいずれにも障害物はなく、またロボットがマス目の外に出ることはありませんでした。

ロボットが置かれたマスと停止したマスの順序対としてありうるものの個数を求めてください。

制約

  • 2 \leq N,M \leq 2\times 10^3
  • s_{ij}# または . である

入力

入力は以下の形式で標準入力から与えられる。

N M
s_{11}...s_{1M}
:
s_{N1}...s_{NM}

出力

ロボットが置かれたマスと停止したマスの順序対としてありうるものの個数を出力せよ。


入力例 1

3 3
..#
...
#.#

出力例 1

9

((1,1),(2,2)),((1,1),(3,2)),((1,2),(2,1)),((2,1),(1,2)),((2,1),(3,2)),((2,2),(1,1)),((2,3),(1,2)),((2,3),(1,1)),((3,2),(2,3))9 個が条件を満たします。


入力例 2

2 5
.#.#.
..#..

出力例 2

2

入力例 3

6 8
#......#
##....##
#.#..#.#
#..##..#
#......#
#......#

出力例 3

182