配点 : 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