迷宫抢救

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

dreaming3000里的张大侠每次都会去他的女朋友那去,每次要发费很多钱,渐渐的他国库空虚,情急之下,在一个现实迷宫游戏公司当任一门电话导航员:在游客求救时,电话指导游客走出迷宫,当然被困游客如果能越早走出,对电话导航员的评价越高,那么他的奖金也就越高,张大侠不愧是参加过ACM的人,他想了想,这个可以写一个程序,但是他忙于dreaming3000的一个项目,没空去写,于是就向你求救。 迷宫设计者在迷宫的每一个地方设计了求救电话;当游客PLMM迷路时,可以通过电话进行求救,并且求救中心可以根据电话号码和这个求救时间得图1这种图形。并显示在电话导航员的电脑上,现在张大侠要知道这位游客PLMM在他的指导下最少要多少步才能走出迷宫,不能走出的话,请告诉他"Impossible"! 如果是通的话,游客在每一处都可以有8个方向选择去走。 现在电脑导航员的图片是如“图1”所示。 /*加图1*/

当然事先你要进行迷宫处理;美女位置用字符‘2’表示,不能走的地方用字符‘1’表示,能走的则用‘0’表示。处理后称之为 迷宫“012”图 。迷宫最多99行99列; 例如: /*加图2*/

处理之后为: 0101010 1000101 1100010 1001201 1010110 1000001 0100100

Input

第1行输入一个整数 n是表示PLMM求救人数,(测试n次) 下面是迷宫“012”图 以‘#’表示迷宫图处理完了。

Output

对任意不大于99行99列的迷宫;能走出去的话输出最少步数;否则,请输出"Impossible",每一次求救,输出占一行;

Sample Input

3
0101010
1000101
1100010
1001201
1010110
1000001
0100100
#
011111
110201
101011
111111
#
1020110000001
0100111100000
#

Sample Output

The least step is:2
Impossible
The least step is:0

Hint

Source

dreaming3000

提交代码