[Bulgarian2015组队赛]frobot
题目描述
一个小机器人需要探索一块很大的矩形区域。该区域被分成东西、南北方向排列的正方形格子，并由两个互相嵌套的矩形边界围成：外层矩形是区域外边界，内层矩形是一个不可进入的“洞”。
两个矩形的顶点都位于网格点上，边与网格线重合，且内层矩形与外层矩形没有公共点。
机器人的任务是访问研究区域中的所有格子。机器人不能走出区域，也不能进入内层矩形内部；但是同一个格子可以被访问多次。
机器人有一个指南针，能准确知道四个方向：
N：北；S：南；W：西；E：东。
机器人每一步只能向上述四个方向之一移动到相邻格子，即移动到与当前格子有公共边的格子。
不过，机器人的能力非常有限：
- 它很“近视”：在某个格子中时，只能知道四个方向中哪些方向存在相邻的合法格子；
- 它严重“健忘”：进入某个格子后，只记得自己刚才是从哪个方向移动进入当前格子的；
- 除此之外，它不记得自己走过的路径、访问过哪些格子、当前位置在哪里等任何信息；
- 第一步时，机器人没有“上一步移动方向”的信息。
因此，机器人在某个格子中决定下一步方向时，只能依赖以下信息：
- 上一步进入当前格子时的移动方向；
- 当前格子的合法相邻方向集合。
你需要编写程序 frobot，向标准输出打印一组行动协议。该协议应能保证：对于测试中的每个区域、初始位置和燃料限制，机器人按照你的协议行动后，能够访问该区域内的所有格子至少一次。
你不知道测试中矩形的大小、内层矩形的位置，也不知道机器人初始在哪个合法格子中。初始格子视为已经访问。
机器人燃料有限：每个测试点会给出一个允许的最大移动步数。燃料耗尽后立即检查是否已经访问所有格子。
输入格式
本题程序不需要读取任何输入。
在本 Hydro 配置包中，所有测试点的标准输入均为空。地图配置由 SPJ 隐藏读取，选手程序不应依赖任何输入。
输出格式
程序应输出若干行，每行表示一条协议规则，格式如下：
<上一步方向>,<可走方向集合>:<下一步决策>
其中：
<上一步方向>是一个字符，只能是X、N、S、W、E之一；X表示没有上一步方向信息，只会在决定第一步时出现；<可走方向集合>是由若干个大写字母N、S、W、E组成的字符串，表示当前格子中哪些方向存在合法相邻格子；<下一步决策>是一个字符，只能是X、N、S、W、E之一；- 决策中的
X表示停止移动； - 其他字符表示向对应方向移动一步。
所有字母均为大写英文字母。
例如：
X,SE:E
表示：如果当前是第一步，且当前格子南、东方向存在合法相邻格子，则机器人下一步向东移动。
方向集合中字母顺序不影响含义，例如 NE 与 EN 表示同一种相邻方向集合。
协议错误说明
协议可能出现两类错误。
强错误：矛盾规则
如果协议中对同一种状态给出了不同决策，则为强错误。此时整次提交得分为 0。
例如：
X,EN:N
X,NE:E
这两行描述的是同一种情况：第一步，且北、东方向可走。但第一行要求向北走，第二行要求向东走，二者矛盾。
弱错误：缺少规则
如果协议本身没有矛盾，但在某个测试点的模拟过程中，机器人遇到了一种没有被协议覆盖的状态，则该测试点得分为 0。
评分方式
评测程序会在多个不同区域、不同初始位置和不同燃料限制下模拟机器人的运动。
对于每个测试点，机器人运动会在以下情况之一发生时结束：
- 达到该测试点允许的最大步数；
- 协议给出的下一步决策为
X，即要求停止。
停止后，评测程序检查是否访问了该区域内所有合法格子。
- 若全部访问，获得该测试点分数；
- 否则该测试点不得分。
本题配置包中共有 21 个测试点，每个测试点约占 100 / 21 分。
样例协议
下面是一组协议示例：
X,SE:E
N,NS:N
E,EW:E
E,WS:S
S,NS:S
S,NW:W
E,NEW:N
W,EW:W
W,EN:N
N,SE:X
样例解释
上述协议中没有矛盾规则。
对于某些特定区域，如果机器人从西北角开始，该协议可能能够很好地工作。但如果机器人从其他位置开始，协议可能缺少对应的第一步规则，从而成为弱错误。
例如，如果增加规则：
X,EW:W
机器人就可以从第一行的第二个或第三个格子开始行动。但这仍不一定保证访问所有格子。若从第三个格子开始，第一行第二个格子可能永远不会被访问。
将最后一行：
N,SE:X
改为：
N,SE:E
可以修复其中一种情况。此时协议可能没有主动停止规则，但这不是必须的，因为机器人也会在燃料耗尽时停止。
经过一些改进后，下面这组协议可以在该示例区域中从任意合法起点工作：
X,SE:E
X,EW:W
X,SW:S
X,SN:S
X,NW:W
X,NE:N
N,NS:N
E,EW:E
E,WS:S
S,NS:S
S,NW:W
W,EW:W
W,EN:N
N,SE:E
S,NE:N
W,SE:E
但仍然可以构造出其他合法区域，使这组协议无法完成任务。
图片说明
含有一张示意图，用于展示由外层矩形和内层矩形围成的环形网格区域，以及样例协议对应的示例区域。