Escape from Tetris

由于整日整夜地对着这个棋盘，Lele终于走火入魔。每天一睡觉，他就会梦到自己会被人被扔进一个棋盘中，一直找不到出路，然后从梦中惊醒。久而久之，Lele被搞得精神衰弱。梦境是否会成为现实，谁也说不准，不过不怕一万只怕万一。现在Lele每次看到一个棋盘，都会想象一下自己被关进去以后要如何逃生。<br><br>Lele碰到的棋盘都是正方形的，其中有些格子是坏的，不可以走，剩下的都是可以走的。只要一走到棋盘的边沿（最外面的一圈），就算已经逃脱了。Lele梦见自己一定会被扔在一个可以走的格子里，但是不确定具体是哪一个，所以他要做好被扔在任意一个格子的准备。<br><br>现在Lele请你帮忙，对于任意一个棋盘，找出一个最短的序列，序列里可以包括&quot;north&quot;(地图里向上),&quot;east&quot;(地图里向右),&quot;south&quot;(地图里向下),&quot;west&quot;(地图里向左)，这四个方向命令。不论Lele被扔在棋盘里的哪个好的格子里，都能按这个序列行走逃出棋盘。<br>逃脱的具体方法是：不论Lele被扔在哪里，Lele按照序列里的方向命令一个一个地走，每个命令走一格，如果走的时候会碰到坏的格子，则忽略这条命令。当然，如果已经逃脱了，就可以不考虑序列中剩下的命令了。<br>

本题目包含多组测试，请处理至文件结束。<br>每组测试第一行包含一个正整数 N (0<N<9)，代表棋盘的大小是 N*N<br>接下来有N行，每行N个字符代表这个棋盘。<br>其中0代表该位置是好的，可以走，1代表该位置是坏的，不可以走。<br><br>题目数据保证，对于任意一个棋盘，都存在题目中所要求的序列<br>

对于每组数据，输出题目所要求的序列，序列中每个元素一行。<br>如果存在两个符合要求的序列，请输出字典序最小的那个序列。<br><br>两个测试之间请用一个空行隔开。<br>

4<br>1101<br>0001<br>1100<br>1001<br>

east<br>north<br>

linle

HDOJ 2007 Summer Exercise（2）