9 · 午枫爱迷宫 · GESP考级

题目描述

小午和小枫掉入了一个大小为 $n\times m$ 的充满陷阱的迷宫，小枫不幸被机关锁住了，迷宫中有一把可以打开锁住小枫机关的钥匙、一些墙壁、一些安全的道路、一些较高的障碍物和一个出口。 小午现在知道了整个迷宫样貌，他用不同的符号把整个迷宫画了下来，其中各个符号所代表的意义如下： . ：表示安全的道路。 # ：表示墙壁。 N ：表示小午所在位置。 M ：表示小枫所在位置。 ! ：表示钥匙。 $ ：表示较高的障碍物。 @ ：表示出口。 其中 N 、M 、! 、@ 所在位置也视为一个安全的道路，所以当小午或小枫走到这些位置时并不会受到任何的限制。 小午和被解救的小枫每次可以走到其相邻的道路，比如，若当前位置为 $(x,y)$ ，则其在不受阻的前提下可以移动到 $(x+1,y)$，$(x-1,y)$，$(x,y+1)$，$(x,y-1)$ 这四个位置的其中一个。 由于小午身材矮小，无法通过那些较高的障碍物，但是小枫可以带他一起翻越那些障碍物，所以如果小午想通过那些障碍物的话必须先解救小枫。 小午想知道他能否解救小枫并和他一起逃出这个迷宫，当然，如果小午想尽一切方法也无法解救小枫但自己可以逃出迷宫的话，他会选择抛弃小枫独自逃出迷宫。

第一行输入两个正整数 $n,m$ $(1\leq n, m \leq 10^3)$ 表示迷宫的行数和列数 。 接下来 $n$ 行，每行 $m$ 个字符 $s_{i,j}$ ，保证 $s_{i,j} \in \{$.,#,N,M,!,$`,`@`$\}$，其中 N，M，!，@` 保证有且仅有一个。

输出一行字符串，如果小午可以解救小枫并一起逃出迷宫，输出 we were here together ；如果小午无法解救小枫，但可以自己独自逃出迷宫的，输出 sorry ；如果两人都无法逃出迷宫，输出 NO 。

输入 #1

4 6
N..!#M
##..#.
@##...
$$$.##

输出 #1

we were here together

输入 #2

3 4
N.#M
.##.
@##!

输出 #2

sorry

输入 #3

3 6
N..!#M
###$..
@...##

输出 #3

NO