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

 在 $n$ 行 $m$ 列的矩形空间中有一个机器人。矩形空间的每一个格子要么是平地（用半角点号 `.` 表示），要么是障碍物 （用井号表示 `#`）。以下是一个 $n = 3, m = 7$ 的例子： ``` ...#... ...#... ....... ``` 初始时,机器人位于矩形的左上角 （第一行、第一列）。每一时刻，机器人可以遵照程序执行 `U`（Up，向上）、`L` （Left，向左）、 `D` （Down，向下）、`R` （Right，向右） 四种指令中的一个，尝试向某个方向移动一格；如果移动的目标格子超出了边界或是障碍物，则保持原地不动，例如执行程序： `LLLRRRRRRRRRDDDDRRRRRRRRR` 后，机器人会从空间的左上角移动到右下角。Dr. X 扩展了机器人程序的表达能力,引入了循环。给定程序 `P`，`(P)n` 相当于把程序 `P`“复制粘贴”$n$ 次。循环可以嵌套。例如，在足够大且无阻挡的空间中执行程序： `(R(DRUL)7)5` 会重复 $5$ 次执行“向右移动一格、转圈 $7$ 次”，而如果机器人在 $n = 1, m = 2$ 的空间中执行上述程序，就会表现为“左右横跳”。 Dr. X 还给机器人装备了人工智能，对于某些指定的循环，机器人可以由深度神经网络自主决定循环的次数（$0$ 次或任意多次），用星号 `*` 表示，例如 `(DR(R)*)3` 外层循环会执行 $3$ 次，由于循环“复制粘贴”的特性，每次向下向右移动一格后，机器人可以根据自己的想法向右移动 $0$ 格或任意多格。人工智能循环也可以嵌套，根据循环“先外层后里层”的执行顺序，总是先确定外层人工智能循环的执行次数，再按照“复制粘贴”的规则执行内层循环代码。 人工智能模块使机器人的行为变得难以预测。给定一个机器人程序，Dr. X 想知道，哪些格子是机器人在执行程序过程中绝无可能经过的（即无论机器人如何选择循环执行的次数，都不会经过）？这样他可以在这些格子上安装监控，并在观察到机器人行为失控的时候及时制止。

输入第一行两个空格分隔的整数 $n$ 和 $m$，代表矩形空间的大小为 $n$ 行、$m$ 列。 接下来 $n$ 行，每行 $m$ 个字符，描述了矩形空间。其中半角点号为平地、井号为障碍物。 输入最后一行是一个字符串，为机器人执行的程序。程序由 $\tt{U/L/D/R}$、圆括号、正整数、星号组成。输入程序保证合法：圆括号总是正确配对，且之后紧跟一个正整数或一个星号。除此之外，程序中所有的字符都是 $\tt{U,L,D}$ 或 $\tt{R}$。机器人初始时位于左上角，输入保证左上角不是障碍物。**固定次数循环的次数总是在 $1$ 到 $9$ 之间。**

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

对于 $30\%$ 的数据，输入程序不含星号 `*` 且在 $10^5$ 步内终止。 对于另外 $30\%$ 的数据，输入程序中不含星号 `*`。 对于 $100\%$ 的数据，$1 \leq n, m \leq 10$，且输入程序的长度不超过 $1000$。 >本题原始满分为 $20\text{pts}$。