AT_mujin_pc_2018_c 右折

有一个 $N$ 行 $M$ 列的网格。自上而下的第 $i$ 行，自左而右的第 $j$ 列的格子记作 $(i, j)$。特别地，左上角的格子是 $(1, 1)$，右下角的格子是 $(N, M)$。网格的状态由一个二维数组 $s$ 表示，当 $s_{ij}$ 为 `#` 时，表示格子 $(i, j)$ 上有障碍物；为 `.` 时，表示没有障碍物。 高桥君在这个网格的某个格子上放置了一个机器人，并让机器人朝上下左右任意一个方向。机器人会沿着它面朝的方向直走至少 $1$ 格，然后向右转 $90$ 度，再沿新方向直走至少 $1$ 格后停下。在这个过程中，机器人经过的所有格子（包括起始格和停止格）都没有障碍物，且机器人不会走出网格。 请你计算，机器人可能的起始格和停止格的有序对的数量。

输入以如下格式从标准输入读入： > $N$ $M$ > $s_{11}\ldots s_{1M}$ > $s_{21}\ldots s_{2M}$ > $\vdots$ > $s_{N1}\ldots s_{NM}$

输出机器人可能的起始格和停止格的有序对的数量。

## 限制条件 - $2 \leq N, M \leq 2 \times 10^3$ - $s_{ij}$ 只会是 `#` 或 `.` ## 样例解释 1 $((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$ 个满足条件的有序对。 由 ChatGPT 4.1 翻译