Escape from Tetris

Time Limit: 12000/4000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

由于整日整夜地对着这个棋盘,Lele终于走火入魔。每天一睡觉,他就会梦到自己会被人被扔进一个棋盘中,一直找不到出路,然后从梦中惊醒。久而久之,Lele被搞得精神衰弱。梦境是否会成为现实,谁也说不准,不过不怕一万只怕万一。现在Lele每次看到一个棋盘,都会想象一下自己被关进去以后要如何逃生。

Lele碰到的棋盘都是正方形的,其中有些格子是坏的,不可以走,剩下的都是可以走的。只要一走到棋盘的边沿(最外面的一圈),就算已经逃脱了。Lele梦见自己一定会被扔在一个可以走的格子里,但是不确定具体是哪一个,所以他要做好被扔在任意一个格子的准备。

现在Lele请你帮忙,对于任意一个棋盘,找出一个最短的序列,序列里可以包括"north"(地图里向上),"east"(地图里向右),"south"(地图里向下),"west"(地图里向左),这四个方向命令。不论Lele被扔在棋盘里的哪个好的格子里,都能按这个序列行走逃出棋盘。
逃脱的具体方法是:不论Lele被扔在哪里,Lele按照序列里的方向命令一个一个地走,每个命令走一格,如果走的时候会碰到坏的格子,则忽略这条命令。当然,如果已经逃脱了,就可以不考虑序列中剩下的命令了。

Input

本题目包含多组测试,请处理至文件结束。
每组测试第一行包含一个正整数 N (0<N<9),代表棋盘的大小是 N*N
接下来有N行,每行N个字符代表这个棋盘。
其中0代表该位置是好的,可以走,1代表该位置是坏的,不可以走。

题目数据保证,对于任意一个棋盘,都存在题目中所要求的序列

Output

对于每组数据,输出题目所要求的序列,序列中每个元素一行。
如果存在两个符合要求的序列,请输出字典序最小的那个序列。

两个测试之间请用一个空行隔开。

Sample Input

4 1101 0001 1100 1001

Sample Output

east north

Hint

lcy

Source

HDOJ 2007 Summer Exercise(2)

提交代码