T313423 幻想乡智能大赛

**这是一道交互题**。

命莲寺的众人为了吸引参拜客来参拜，造了一个 $n\times m$ 的迷宫，迷宫外围是一层墙壁。第一个到达终点的人，可以获得宝贝。 于是幻想乡里的妖怪神仙全来这里大显神通。不过对门的神灵庙一众不乐意了：生意都被抢走了！ 所以神灵庙打算来砸场子。具体方式是首先到达终点抢到宝贝。 迷宫起点在 $(1,1)$ 位置，需要到达 $(n,m)$ 位置，每一回合可以向前后左右四个位置移动。 然而命莲寺众人不会轻易地让选手获得奖品，所以设下了结界，在任何位置只能看到前后左右四个方向有没有墙。对于这道题而言，你只能通过交互器来判定四周的情况。在刚进入迷宫时，以及每一步行动后，交互器将会告诉你四周墙壁的情况。格式见「交互细节」处。 现在需要花**尽可能少的步数**到达终点。如果不可能到达终点，请输出 $\texttt{Baka}$。 --- 这和人工智能有什么关系？ 专业小偷霍青娥从命莲寺偷到了迷宫构造器，并且造了一个有 $10000$ 组数据的大样例，实际迷宫使用相同的构造器制造。可以使用这些数据训练你的程序。 ### 交互细节 对于每一组数据，在你第一次行动前，以及每次行动后，你将得到一些输出提示你周围墙壁的情况： - 如果你得到的输出是 $-1$，那么说明你进入了墙内。请立即终止程序，以防出现与预期相悖的事情。 - 否则你将得到四个整数 $x_1,x_2,x_3,x_4$。 - 如果 $x_1=1$，那就说明正上方有一堵墙壁，否则值为 $0$ 表示没有墙壁； - 如果 $x_2=1$，那就说明正右方有一堵墙壁，否则值为 $0$ 表示没有墙壁； - 如果 $x_3=1$，那就说明正下方有一堵墙壁，否则值为 $0$ 表示没有墙壁； - 如果 $x_4=1$，那就说明正左方有一堵墙壁，否则值为 $0$ 表示没有墙壁。 - 当你到达 $(n,m)$ 位置后，此轮胜利。交互库会立即终止，你的程序也应该立即退出。同时，你不应该输出任何多余的东西。

_这里描述的是下发的 `maze.data` 的格式_。 第一行有一个正整数 $T$，表示数据组数。对于每组数据， - 第一行有两个整数 $n,m$，描述迷宫的大小。 - 接下来 $n$ 行，每行有 $m$ 个字符 $\verb!#!$ 或者 $\verb!.!$。如果为 $\verb!#!$ 则表示此处是一个墙壁，否则是空气。

每一次行动时，你可以输出以下 $4$ 个字符串之一来移动： - $\mathtt{North}$：向正上方移动一格； - $\mathtt{South}$：向正下方移动一格； - $\mathtt{West}$：向正左方移动一格； - $\mathtt{East}$：向正右方移动一格。 特别地，如果你根据已有信息断定迷宫一定没有路径，请输出 $\verb!Baka!$。

### 样例解释 样例给出的迷宫如下图所示： ```plain .#.# ...# ##.. #.#. ``` ### 判分方式 记从 $(1,1)$ 到达 $(n,m)$ 的最短路径长度为 $d_0$。你走过的路径长度为 $d_1$。 - 若 $|d_1-d_0|\le 6$，你将获得该测试点全部分数； - 若 $|d_1-d_0|\le 10^3$，你将获得该测试点 $50\%$ 分数； - 若 $|d_1-d_0|\le 10^6$，你将获得该测试点 $10\%$ 分数； - 否则，你将不能获得任何分数。 ### 数据范围及约定 - 对于 $20\%$ 的数据，$1\le n,m\le 3$； - 对于 $40\%$ 的数据，$1\le n,m\le 5$； - 对于 $80\%$ 的数据，$1\le n,m\le 24$； - 对于全部数据，$1\le n,m\le 128$。