← 返回题目列表

Codeforces · 683/J

J. 炸弹英雄

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

在一款新的电脑游戏中,你需要帮助英雄走出迷宫,迷宫是一个大小为 n × m 的矩形区域。英雄位于该区域的一个单元格中。他知道迷宫的出口在哪里,他也想到达那里。

在一次移动中,英雄可以移动到下一个空闲的单元格(即与当前单元格有共同面的单元格),或者在他所在的单元格上放置炸弹,或者跳过该移动而不执行任何操作。放置的炸弹会在三个动作后爆炸,即英雄再进行 3 个动作但没有时间进行第四个动作后(上述所有三种类型的动作都被视为动作)。

爆炸摧毁了与该单元至少有一个公共点的所有单元中的障碍物(即与炸弹单元共享一个角或一侧的所有单元中)。爆炸不能伤害有出口的牢房或有英雄的牢房。英雄不能超越迷宫的界限。

你的任务是确定英雄到达出口的行动顺序。请注意,您不必最小化序列的长度。唯一的限制 — 结果序列的长度不应超过 100,000 个符号。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100, n·m > 1) — 迷宫的大小。

以下n行每行包含m个字符——迷宫的描述。字符“。”表示空闲单元,“E”- 英雄,“T”- 出口,“X”- 障碍物。

保证迷宫中只有一名英雄和一个出口。

输出

打印英雄的行动,这将帮助他走出迷宫(“M” - 放置炸弹,“T” - 跳过移动,“S” - 向下,“W” - 向左走,“N” - 向上,“E” - 向右走)。如果英雄无法到达出口,则打印“无解决方案”(不带引号)。

生成的序列的长度不应超过 100,000 个符号。如果有多个解决方案,则允许打印其中任何一个。

示例

输入 #1

3 5
XEX.X
X.XXT
X.X.X

输出 #1

SSMNNTSSNEMWWTEEEE