#961. [信息与未来 2024] AI 机器人

[信息与未来 2024] AI 机器人

题目描述

nnmm 列的矩形空间中有一个机器人。矩形空间的每一个格子要么是平地(用半角点号 . 表示),要么是障碍物 (用井号表示 #)。以下是一个 n=3,m=7n = 3, m = 7 的例子:

...#...
...#...
.......

初始时,机器人位于矩形的左上角 (第一行、第一列)。每一时刻,机器人可以遵照程序执行 U(Up,向上)、L (Left,向左)、 D (Down,向下)、R (Right,向右) 四种指令中的一个,尝试向某个方向移动一格;如果移动的目标格子超出了边界或是障碍物,则保持原地不动,例如执行程序:

LLLRRRRRRRRRDDDDRRRRRRRRR

后,机器人会从空间的左上角移动到右下角。Dr. X 扩展了机器人程序的表达能力,引入了循环。给定程序 P(P)n 相当于把程序 P“复制粘贴”nn 次。循环可以嵌套。例如,在足够大且无阻挡的空间中执行程序:

(R(DRUL)7)5

会重复 55 次执行“向右移动一格、转圈 77 次”,而如果机器人在 n=1,m=2n = 1, m = 2 的空间中执行上述程序,就会表现为“左右横跳”。

Dr. X 还给机器人装备了人工智能,对于某些指定的循环,机器人可以由深度神经网络自主决定循环的次数(00 次或任意多次),用星号 * 表示,例如

(DR(R)*)3

外层循环会执行 33 次,由于循环“复制粘贴”的特性,每次向下向右移动一格后,机器人可以根据自己的想法向右移动 00 格或任意多格。人工智能循环也可以嵌套,根据循环“先外层后里层”的执行顺序,总是先确定外层人工智能循环的执行次数,再按照“复制粘贴”的规则执行内层循环代码。

人工智能模块使机器人的行为变得难以预测。给定一个机器人程序,Dr. X 想知道,哪些格子是机器人在执行程序过程中绝无可能经过的(即无论机器人如何选择循环执行的次数,都不会经过)?这样他可以在这些格子上安装监控,并在观察到机器人行为失控的时候及时制止。

输入格式

输入第一行两个空格分隔的整数 nnmm,代表矩形空间的大小为 nn 行、mm 列。

接下来 nn 行,每行 mm 个字符,描述了矩形空间。其中半角点号为平地、井号为障碍物。

输入最后一行是一个字符串,为机器人执行的程序。程序由 U/L/D/R\tt{U/L/D/R}、圆括号、正整数、星号组成。输入程序保证合法:圆括号总是正确配对,且之后紧跟一个正整数或一个星号。除此之外,程序中所有的字符都是 U,L,D\tt{U,L,D}R\tt{R}。机器人初始时位于左上角,输入保证左上角不是障碍物。固定次数循环的次数总是在 1199 之间。

输出格式

输出 nn 行,每行 mm 个字符,按顺序输出矩形空间中每个格子的计算结果。如果是障碍物格子,输出井号 #。如果是机器人选择适当的循环次数可以到达的平地格子,输出加号 +。否则输出半角点号 .

3 7
...#...
...#...
.......
LLLRRRRRRRRRDDDDRRRRRRRRR
+++#...
..+#...
..+++++
3 7
...#...
##.....
.......
(R(DRUL)7)5
+++#...
##+++++
..+++++
3 7
.......
.#####.
.......
(R)*(D)*
+++++++
+#####+
+.....+

提示

对于 30%30\% 的数据,输入程序不含星号 * 且在 10510^5 步内终止。

对于另外 30%30\% 的数据,输入程序中不含星号 *

对于 100%100\% 的数据,1n,m101 \leq n, m \leq 10,且输入程序的长度不超过 10001000

本题原始满分为 20pts20\text{pts}