P6259 [ICPC 2019 WF] Karel the Robot

### Warning: If you submit a malicious program, you will be banned. ### 警告：恶意提交本题将被封号。

你知道“机器人”这个词已经快 100 年了吗？它首次出现在 1920 年，由 Karel Capek 编写的科幻戏剧 $R.U.R.$ 中。为了向这位捷克作家致敬，许多年后斯坦福大学将一种教育编程语言命名为 Karel。你的任务是实现这种编程语言的简化版本的解释器。 Karel 编程语言控制一个名叫 Karel 的机器人，它生活在一个单位方格的网格中。一些方格是空的，而另一些则包含障碍物。Karel 总是占据一个空的方格，并面向四个基本方向之一。两个基本命令是“前进”和“左转”。该语言还提供简单的条件和循环语句。该语言的主要教育潜力在于可以定义新的过程来完成更复杂的任务。 我们的简化版本的语言可以通过以下语法描述： ```plain := "" | := "m" | "l" | | "i" "(" ")(" ")" | "u" "(" ")" := "b" | "n" | "s" | "e" | "w" := := "=" ``` 有五种类型的命令： - $\texttt m$（“前进”）使 Karel 在其当前方向上前进一个网格单元，除非前方有障碍物，在这种情况下命令无效。 - $\texttt l$（“左转”）使 Karel 左转 $90$ 度。 - $\texttt X$，其中 $\texttt X$ 是任何大写字母，调用名为 $\texttt X$ 的过程。 - $\texttt i$（“如果”）后跟一个单字母条件和两个括号中的程序。如果条件满足，则执行第一个程序。否则，执行第二个程序。 - $\texttt u$（“直到”）后跟一个单字母条件和一个括号中的程序。如果条件满足，则不执行任何操作。否则，执行程序，然后重复该命令。 条件可以是 '$b$'，当且仅当在 Karel 当前方向的下一个方格中有障碍物时满足，或者是四个方向字母之一 `n`、`s`、`e` 或 `w`，当且仅当 Karel 当前方向分别为北、南、东或西时满足。 例如，一个简单的程序 `ub(m)` 可以理解为：“一直前进直到遇到障碍物”，而 `un(l)` 意味着“转向北”。过程定义 `R=lll` 定义了一个新过程 `R`，其有效含义是“右转”。

输入的第一行包含四个整数 $r, c, d$ 和 $e$，其中 $r$ 和 $c$ $(1 \leq r, c \leq 40)$ 是 Karel 所在网格的维度，$d$ $(0 \leq d \leq 26)$ 是过程定义的数量，$e$ $(1 \leq e \leq 10)$ 是要执行的程序数量。 接下来是 $r$ 行描述网格（从北到南），每行包含 $c$ 个字符（从西到东），每个字符要么是 `.`（表示空方格），要么是 `#`（表示障碍物）。该给定区域外的所有方格都被视为障碍物，这意味着 Karel 永远不能离开该区域。 接下来的 $d$ 行中的每一行包含一个过程定义，将一个过程名称（一个大写字母）与形成过程主体的程序关联。没有过程名称被定义多于一次。过程主体可以包含尚未定义的过程调用。 最后 $2e$ 行描述要执行的程序。每个这样的描述由一对行组成。每对的第一行包含两个整数 $i$ 和 $j$ 以及一个字符 $h$，其中 $i$ $(1 \leq i \leq r)$ 是行，$j$ $(1 \leq j \leq c)$ 是 Karel 的初始位置的列，$h \in \{ \texttt n, \texttt s, \texttt e, \texttt w\}$ 表示 Karel 的初始方向。保证初始位置是一个空方格。每对的第二行包含一个要从该初始位置执行的程序。 所有过程主体和所有要执行的程序长度至少为 $1$ 且最多为 $100$ 个字符，语法正确，并且只包含已定义的过程调用。包含过程定义和要执行的程序的行不包含空格字符。

对于每个程序执行，输出从各自初始位置执行完整程序后 Karel 的最终位置。遵循用于描述初始位置的格式，即两个数字和一个方向字符。如果某个执行永远不会终止，则输出 `inf`。

来源：ICPC 世界总决赛 2019。 题面翻译由 ChatGPT-4o 提供。