← 返回题目列表

AtCoder · nupc2024_o

O. LRUD 迷宫

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

配点 : 100 点

問題文

縦 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 \le i \le N 和 1 \le j \le M , (i,j) 中写入的字符 L , R , U , D 出 重写为与 S_{i,j} 不同的字符。

此操作是 3NM 有不同的类型。 其中,“运行后并网 找出可以到达 (1,1) 从 (N,M) 的物体数量。

制約

  • 2 \le N,M \le 1000
  • N,M 是一个整数 如果不可能将棋子放置在
  • S_{i,j} 为 L , R , U , D 任何一个

入力

输入是按以下格式从标准输入给出的。

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 3
RDD
RLD
URU

出力例 1

3

下面 3 类型满足条件。 更改为

  • (1,2) 分成 R 更改为
  • (2,2) 分成 R 更改为
  • (2,2) 分成 D 更改为

入力例 2

3 3
UUU
RRR
DDD

出力例 2

0

答案是 也可能是 0 。


入力例 3

3 4
RDUU
LRDD
ULRU

出力例 3

22