UOJ Logo Universal Online Judge

UOJ

#247. 【Rujia Liu's Present 7】Mysterious Space Station

附件下载 统计

公元 3000 年,科学家发现了一个神秘的太空站。经过几个月的研究之后,他们作出了一张电子地图并发送了一个机器人过去进行进一步调查。

这张地图由 $n \times m$ 的方格组成,每个格子上为空或有障碍物,每次可以从东西南北四个方向中选择一个方向,发送指令让机器人向该方向移动一个格子。然而,这个空间站里没有光,所以机器人只能在黑暗中乱走乱撞。当机器人试图移动到障碍物上时此次移动便会失败,可据此推断出前方是否有障碍物。

这张地图还有一个特别的地方:所有的障碍物都是四连通的(通过东西南北四个方向连通),并且所有空格子被障碍物包围。所有的空格子之间均可互相到达,并且该空间站不存在通道。不存在通道的意思是,对于每个空格子,南北两个相邻格子中至多只有一个障碍物,东西两个相邻格子中至多只有一个障碍物。

我们将所有的空格子从北到南、从西到东依次编号为 $1, 2, 3, \dots$,如下图所示:

图1

有 $k$ 个传送控制器,每个控制器连接了两个不同的空格子,称为传送格。每个传送格仅可最多与一个传送控制器连接,并且传送格的 $8$ 个相邻格子不可能是另一个传送格或障碍物。

如果两个传送格由同一个控制器连接,那么机器人一旦从某个方向走到了其中一个格子,它就会立刻被传送到另一个格子上,并且以同样的方向移动到相邻格子上。显然这个过程中机器人不会再次被传送。

现在,科学家已经将机器人发送到某一个特定的格子上。由于一些技术上的原因,起始的格子总是与一个障碍物相邻。

例如在上图中,机器人可能会被发送到 $12$ 号格子。如果没有传送控制器,那么向机器人发送指令 EN 后,机器人最后会停在 $8$ 号格子。但再向机器人发送 N 指令时,机器人将被障碍物堵住。如果 $10$ 号格子和 $13$ 号格子之间有一个传送控制器,那么机器人就可以成功地执行 ENN 指令,实际的移动路线为 $12 \rightarrow (13 \rightarrow 10 \rightarrow) 11 \rightarrow 5 \rightarrow 1$。(EWSN 分别代表东西南北四个方向)

你的任务是发送指令控制这台机器人,在合理的移动指令个数内发现所有传送控制器的位置。

交互格式

本题是一道交互式试题,你的程序需要和交互程序通过标准输入输出进行交互。每次向标准输出打印了一行后,请立即刷新缓冲区

第一行三个正整数 $n, m, k$。

接下来 $n$ 行,每行 $m$ 个字符。其中 “.” 表示空格子,“*” 表示障碍物,“S” 表示起始位置。

选手程序需要输出若干 MoveRobot 命令进行移动并读取交互程序返回的移动结果,最后输出恰好 $k$ 个 Answer 命令提交答案。

命令 描述
MoveRobot $D$试图向方向 $D$ 移动,若成功返回 $1$,若失败返回 $0$。
Answer $\mathrm{pos}_1$ $\mathrm{pos}_2$告诉交互程序你找到了一个连接 $\mathrm{pos}_1$ 和 $\mathrm{pos}_2$ 的传送控制器,该命令不返回任何信息。

注意每个传送控制器应被输出恰好一次,但可以按任意顺序。

样例一

交互程序输出 选手程序输出
7 8 1
********
*****..*
***....*
*.....**
*S.....*
*......*
********
MoveRobot E
1
MoveRobot N
1
MoveRobot N
1
MoveRobot W
0
MoveRobot N
0
MoveRobot E
1
MoveRobot E
0
Answer 10 13

限制与约定

保证 $6 \le n,m \le 15$,$1 \le k \le 5$。

MoveRobot 命令的调用次数不能超过 $32767$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

来源

Uva Online Judge,WC2002,题目作者刘汝佳。

特别鸣谢:Renshen Wang, Md. Mahbubul Hasan