← 返回题目列表

AtCoder · mujin_pc_2018_c

C. 右折

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

配点 : 400 点

問題文

N 行 M 有一个列网格。从上面 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