题目描述

Dr. X 把他的机器人超时空传送到了一个未知的空间，也不知道机器人的初始位置和方向。Dr. X 只知道这个未知的空间可以看作由方格组成的矩形方阵，其中的每个方格要么是障碍物，要么是空地。Dr. X 很想知道空间的结构，因此他打算让机器人探索这个空间，并绘制出迷宫的地图。

Dr. X 每次可以给他的机器人发送一条指令，并等待机器人反馈。指令有三种：

• $\tt LEFT$，向左旋转 $90$ 度。机器人会返回旋转后的方位（$\tt E, W, S, N$ 分别表示东、西、南、北）。
• $\tt RIGHT$，向右旋转 $90$ 度。机器人会返回旋转后的方位（$\tt E, W, S, N$ 分别表示东、西、 南、北）。
• $\tt GO$，尝试向前（当前面前的方向）移动到相邻的方格。如果前方的方格是障碍物，机器人会返回 $\tt FAIL$。否则，机器人会返回 $\tt SUCC$ 并移动到到该方格。

你需要编程操纵 Dr. X 的机器人（发送 $\tt LEFT/RIGHT/GO$ 指令），读取机器人的反馈，并在探索完成后绘制出迷宫的地图。

交互方式

本题为交互题，你的程序通过标准输入输出 (键盘输入、屏幕输出) 与另一个程序交互：

while (true) {
  string feedback;
  command = ...; // 确定下一条指令
  cout << command << endl; // 输出一条指令
  cin >> feedback; // 得到机器人的反馈
  if (all_explored) { // 已经探明所有方格
      cout << "END" << endl;
      cout << n << " " << m << endl;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          cout << map[i][j];
        }
        cout << endl;
      }
      break; // 退出循环
  } else {
    ... // 继续探索
  }
}

即你的代码每次输出一行一条指令（$\tt LEFT/RIGHT/GO$），读取机器人的反馈并逐步探测迷宫，直到全部可达的方格都被探明。探索完成后，程序输出 $\tt END$ 表示结束，随后输出迷宫的尺寸和地图，空地用点 $\tt.$ 表示，障碍物用井号 $\tt\#$ 表示。

初始时，Dr. X 并不知道机器人所处的位置。你必须正确探明所有可达的格子，从机器人初始位置不可达的格子，统一认为是障碍物。

输入格式

见「交互方式」。

输出格式

见「交互方式」。

输入输出样例 #1

输入 #1

N

FAIL

W

FAIL

S

FAIL

E

FAIL

输出 #1

LEFT

GO

LEFT

GO

LEFT

GO

LEFT

GO

END
3 3
###
#.#
###

说明/提示

数据范围

对于 $50\%$ 的数据，迷宫中可达的格子不超过 $10$ 行、$10$ 列。

对于 $100\%$ 的数据，迷宫中可达的格子不超过 $100$ 行、$100$ 列。你的程序调用 $\tt GO$ 的次数不得超过 $5\times 10^4$ 次；你的程序输出的迷宫不得超过 $102$ 行、$102$ 列；未探测到的区域无需输出。

提示

你提交的代码存在交互式的循环：

cout << command << endl; // 输出一条指令
cin >> feedback; // 得到机器人的反馈

如果手工输入反馈，测试代码就会变得很困难。如果希望测试你的代码，我们建议将输入（cin>>feedback）替换为模拟实现的机器人反馈函数：

cout << command << endl;
feedback = get_feedback(command);

其中 get_feedback 函数在程序指定得到迷宫中模拟执行 command 命令并返回结果。注意提交前务必将 get_feedback 替换回 cin >> feedback。