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 翻译