← 返回题目列表

AtCoder · icpc2014summer_day4_e

E. 人工智能

中文机器翻译题面 查看原题

问题陈述

已修正问题文(11:18)

已修正问题文和样例输入输出中损坏的一部分符号的表示(11:58)

在盘面上设置了机器人、墙壁和目标,并且给出了描述机器人行动模式的程序.

所给的程序可用以下EBNF表示.

プログラム := {文};
文 := if文|while文|動作文;
if文 := "[", 条件, プログラム, "]";
while文 := "{", 条件, プログラム, "}";
動作文 := "^"|"v"|"<"|">";
条件 := ["~"], "N"|"E"|"S"|"W"|"C"|"T";

“程序”为由多个“语句”组成由0个以上的“语句”组成,如果存在1个以上的语句将从第一个语句开始,按顺序依次执行每个语句。“语句”可以是“动作语句”、“if语句”或“while语句”。“动作语句”为^", "v","<",">中的任意一个,每个执行以下动作.

  • "^": 前進
  • "v": 後退
  • "<“: 向左旋转90度
  • ">“: 向右旋转90度

“如果你判决的话”[“,”条件“,”程序“,,]并按以下顺序执行。

  1. 确定“条件”的内容是否为真
  2. 如果检查正确,执行程序内容并完成该if语句的处理。
  3. 如果判定为α,则结束此if语句的处理

“同时文”为{“,”条件“,”程序“,,}并按以下顺序执行。

  1. 确定“条件”的内容是否为真
  2. 如果判定为真,则执行“程序”的内容,然后返回1
  3. 如果判定为α,则结束此同时文的处理

“条件”为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