# 往届 ACM 队训练题 (参考)

1082. I want out of that maze!

Your’re on holiday in Egypt. Of cause you also visit the pyramids. On your way through the dark lodes, you lost your group and now it’s your job to find a way through the dark maze and find the exit…

Sometimes the exit is very well hidden. So no tourist, even you, can find the way out. If this happens, you can only pray and wait for the next tourist-group - perhaps they may find you.

You will get a map of the whole labyrinth. The maze has the maximal dimension of 100 x 100 fields. You have to find a way through the labyrinth or if there is no way out, you have to print “No way out!”.

There is only two condition for your walk: Your’ re not allowed to pass a field twice and - of cause you can’t walk through walls!

### 输入格式

The first line consists of the dimension of the labyrinth. The first digit stands for the columns and the second describes the number of rows. After this the whole labyrinth will be shown.

1 * stands for a wall - you may not walk through it.

2 . stands for a free way, thats where you can walk

3 Z is your aim, it is the exit of the labyrinth

4 X this is you!

After you’ve passed one labyrinth, another one may follow! The last labyrinth will be recognized by a zero (0) . Every labyrinth may have more than one way out, but of cause it can also have no way out!

### 输出格式

First you’ve to write the number of the labyrinth you’ re just walking through. And then the way you took by orientation. That means, you have to write n(orth), w(est), s(outh) or e(ast).

Another condition is, that you’ve to find the lexicographical shortest way through the maze! That means that every labyrinth may have only one way out, which is correct…

If you find the following ways out, only the first of them is the correct answer:

eeennnessessws

eeeses

enessessen

sseeee

(lexicographically sorted)

If there was no possible way through the labyrinth, you have to print the line ‘No way out!’ and process the next labyrinth if there is another one.

### 样例

Input
18 5
.Z**.*.....*......
..**.*****.*.***.*
*..*.....*...*....
.*.**.*..*..**X**.
......**....*...*.
2 2
X*
*Z
3 4
***
.X.
...
..Z
0

Output
#1: neennwwwwsswsswwwnnwwwsswwwnnwnn
#2: No way out!
#3: ess