CF97D Robot in Basement

教授又一次把他的家用机器人弄丢了。在思考了一番后，教授意识到他把机器人落在了地下室。 教授家的地下室表示为一个 $n \times m$ 的矩形，被划分为 $1 \times 1$ 的方格。有些方格是墙，不可通过；其余方格可以通过。你可以从任意可通过的方格，经过相邻且可通过的方格，走到另一个可通过的方格。其中有一个可通过的方格是地下室的出口。机器人正好被放置在某一个可通过的方格上，机器人也可能一开始就在出口方格上。 教授害怕晚上到黑暗的地下室去找机器人。然而，他有地下室的平面图和机器人的遥控器。通过遥控器，教授可以向机器人发送信号，让它向左、右、上、下移动一个方格。当机器人收到信号时，如果指定方向上相邻的方格可通过，则机器人会朝该方向移动，否则保持原地不动。 教授在纸上写了一串共 $k$ 条指令。他认为这串指令无论机器人的初始位置在哪里，都能把机器人带到地下室的出口。教授又编写了一个机器人，根据纸上的指令操作遥控器。教授正准备运行该程序，然后安心睡觉，这时他突然灵机一动。 每执行一条指令都要消耗一些能量，教授不想月底收到巨额电费账单。因此，他想知道，在他写下的指令序列中，最短的前缀长度是多少，可以保证无论机器人最初在哪个可通过的方格，执行完这一部分指令后，机器人都一定会出现在出口格子上。请你来帮教授解决这个难题。

第一行包含三个整数 $n$、$m$ 和 $k$（$3 \leq n, m \leq 150$，$1 \leq k \leq 10^{5}$）。接下来 $n$ 行，每行有 $m$ 个字符，描述了教授家的地下室："#" 表示墙，不可通过；"." 表示可通过方格；"E" 表示出口（该格子也可通过）。任意两个可通过的格子都是连通的，矩形四周的格子都是墙。出口格子在地下室中唯一。最后一行有 $k$ 个字符，表示教授写下的指令序列，"L"、"R"、"U"、"D" 分别表示左、右、上、下。

输出能够保证不管机器人初始位置如何，最终将机器人带到出口的最短前缀长度。如果教授搞错了，即不存在这样的前缀（包括完整序列），输出 $-1$。如果只有一个可通过的格子且该格子就是出口，输出 $0$。

由 ChatGPT 5 翻译