AT_nupc2024_o LRUD Maze

给定一个由 $N$ 行 $M$ 列组成的网格。自上而下第 $i$ 行、从左到右第 $j$ 列的格子记作 $(i, j)$。每个格子上写有一个字符 `'L'`、`'R'`、`'U'`、`'D'`，表示如下标记。现第 $(i, j)$ 格上写的是 $S_{i,j}$。 在该网格上，如果当前位于格子 $(i, j)$，且该格子中写着字符 $c$，则可以按如下方式移动： - 若 $c = $ `'L'` 且 $j \neq 1$，可以移动到格子 $(i, j-1)$。 - 若 $c = $ `'R'` 且 $j \neq M$，可以移动到格子 $(i, j+1)$。 - 若 $c = $ `'U'` 且 $i \neq 1$，可以移动到格子 $(i-1, j)$。 - 若 $c = $ `'D'` 且 $i \neq N$，可以移动到格子 $(i+1, j)$。 接下来你需要进行**恰好 $1$ 次**如下操作： - 选择整数 $1 \leq i \leq N$ 且 $1 \leq j \leq M$，将 $(i, j)$ 的字符更改为 `'L'`、`'R'`、`'U'`、`'D'` 中与 $S_{i,j}$ 不同的一个字符。 这样一共会有 $3NM$ 种不同的操作。请计算，在所有这些操作中，操作后的网格使得你可以从 $(1,1)$ 移动到 $(N, M)$ 的操作数量是多少。

输入按如下格式从标准输入读入： > $N$ $M$ > $S_{1,1} S_{1,2} \dots S_{1,M}$ > $S_{2,1} S_{2,2} \dots S_{2,M}$ > $\vdots$ > $S_{N,1} S_{N,2} \dots S_{N,M}$

请将答案输出到标准输出的一行。

### 样例解释 1 满足条件的有以下 $3$ 种： - 将 $(1,2)$ 改为 `'R'` - 将 $(2,2)$ 改为 `'R'` - 将 $(2,2)$ 改为 `'D'` ### 样例解释 2 答案也可能为 $0$。 ### 数据范围 - $2 \leq N, M \leq 1000$ - $N，M$ 为整数 - $S_{i,j}$ 仅为 `'L'`、`'R'`、`'U'`、`'D'` 中的一个字母 由 ChatGPT 5 翻译