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