Robot on Grid
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Robot on Grid
题目描述
有 行 列的格点。第 行第 列的格记为。每个格子都可以填入 ,, 中的任意一个字符。一开始每个格子都没有字符。一开始有 个格填入了字符。第 个写入文字的格是,填入的字符是 。
有一个可在上述网格上移动的机器人。机器人在 时,可以移动到 、中的任意一个。但是,如果中写着 ,则只能向移动,如果写着 ,则只能向移动。写着 的情况下都可以任意移动。当机器人的起点是 时,机器人不出网格而到达 的移动路径有几条?
在剩下的格子里填入字符的方法有 种,请输出所有填字符情况下路径条数的总和,模 的结果。
问题:
输入格式
第一行三个整数 ,接下来 行每行两个数字 和一个字符 。
输出格式
一个整数表示答案。
样例 #1
样例输入 #1
2 2 3
1 1 X
2 1 R
2 2 R
样例输出 #1
5
样例 #2
样例输入 #2
3 3 5
2 3 D
1 3 D
2 1 D
1 2 X
3 1 R
样例输出 #2
150
样例 #3
样例输入 #3
5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R
样例输出 #3
139923295
数据范围
- 时必有
- 是
R
,D
,X
之一
样例解释 1
- 有 种情况。
- 是
R
时、到 的路径只有 种。 - 是
D
或者X
时、到 的路径各有 种。 - 故总数是 。
20240611集训
- Status
- Done
- Rule
- IOI
- Problem
- 6
- Start at
- 2024-6-11 19:00
- End at
- 2024-6-11 21:00
- Duration
- 2 hour(s)
- Host
- Partic.
- 14