问题陈述
已修正问题文(11:18)
已修正问题文和样例输入输出中损坏的一部分符号的表示(11:58)
在盘面上设置了机器人、墙壁和目标,并且给出了描述机器人行动模式的程序.
所给的程序可用以下EBNF表示.
プログラム := {文};
文 := if文|while文|動作文;
if文 := "[", 条件, プログラム, "]";
while文 := "{", 条件, プログラム, "}";
動作文 := "^"|"v"|"<"|">";
条件 := ["~"], "N"|"E"|"S"|"W"|"C"|"T";
“程序”为由多个“语句”组成由0个以上的“语句”组成,如果存在1个以上的语句将从第一个语句开始,按顺序依次执行每个语句。“语句”可以是“动作语句”、“if语句”或“while语句”。“动作语句”为^", "v","<",">中的任意一个,每个执行以下动作.
- "^": 前進
- "v": 後退
- "<“: 向左旋转90度
- ">“: 向右旋转90度
“如果你判决的话”[“,”条件“,”程序“,,]并按以下顺序执行。
- 确定“条件”的内容是否为真
- 如果检查正确,执行程序内容并完成该if语句的处理。
- 如果判定为α,则结束此if语句的处理
“同时文”为{“,”条件“,”程序“,,}并按以下顺序执行。
- 确定“条件”的内容是否为真
- 如果判定为真,则执行“程序”的内容,然后返回1
- 如果判定为α,则结束此同时文的处理
“条件”为N", "E", "S", "W", "C", "T是“的其中之一,并且在前面可以加上~。每一条记述表示以下真值。
- 在前面~如果附加α,真实值会被反转。
- "N“: 如果它朝北,那就是真;如果不是,那就是假的
- "E“: 如果它朝东,那是真的;否则,它是假的。
- "S“: 如果它朝南,则为真;若不是,则为假
- "W“: 如果它朝西,则为真;否则,为假。
- "C“:如果你面前有一堵墙,那是真的;如果没有,那就是假的。
- "T“: 永远是真的
机器人最初是, 假设它朝北。机器人无法穿墙,只能穿越空的物体。如果程序尝试执行越墙的动作,机器人不会移动,保持原地。最后,当机器人到达目标时,会停止所有正在运行的程序,即使它们仍在运行。
此时,我想知道机器人到达终点需要多少时间。机器人在处理条件数学或程序读取方面能够非常快速地执行,所以实际动作时间决定因素仅是“动作语句”。 因此,我想知道这个机器人到达终点之前,需要执行多少次“动作语句”。
另外,如果尝试执行穿过墙壁的动作,但实际上“动作语句”的动作未能执行,也视为“动作语句”已被执行。
输入
输入以以下格式给出。
$H$ $W$
$a_{1,1}a_{1,2} \ldots a_{1, W}$
$a_{2,1}a_{2,2} \ldots a_{2, W}$
:
:
$a_{H,1}a_{2,2} \ldots a_{H, W}$
$s$
$H$ 表示盘面的高度,$W$ 表示盘面的宽度。
接下来给出了从正上方看到的盘面状态。此盘面上、下、左、右分别对应北、南、西、东。 每个格子的状态表示为 $a_{i,j}$,其值为以下字符之一。
- "s:机器人(机器人的少年位置。保证该格子没有墙)
- "g:目标
- "#:墙(机器人不能在墙上移动)
- ".:空格子
$s$ 中作为字符串输入给机器人的程序。
约束
- $1 \leq H, W \leq 50$
- $1 \leq s$ 的字符数 $\leq 1{,}000$
- $a_{i, j}$ 是.", "#", "s", "g“中的任意一个
- "s", "g“各自只出现一次
- 如果 $i = 1$ 或 $i = H$ 或 $j = 1$ 或 $j = W$,则 $a_{i,j}$ =#“(保证盘面外周被墙包围)
- 作为 $s$ 给出的程序在语法上是正确的
输出
你能到达的地方是到達するまでに実行した「動作文」の数“如果你够不到它,”-1”。请注意,当尝试执行诸如翻墙之类的动作时,即使“动作语句”实际上并未执行,“动作语句”也被视为已执行(输入示例 1)。
示例输入 1
5 3 ### #g# #.# #s# ### ^<^<vv
样本输入 1 的输出
5
示例输入 2
5 7
#######
#.#g..#
#.###.#
#s....#
#######
{T{~C^}<}
样本输入 2 的输出
17
示例输入 3
5 7
#######
#.#g..#
#.###.#
#s....#
#######
{T{~C^}>}
样本输入 3 的输出
-1