迷宫英雄救美

Time Limit: 1000 ms

Memory Limit: 65535 kb

Description

有一PLMM在玩迷宫时不能走出来了;还好迷宫设计者在每一个地方设计了求救电话;并且可以根据电话号码和这个求救时间得图1这种图形。现在知道每个出口(及在边上,假如美女一开始就在出口不算在出口,要另找出口)都有一个想要英雄救美得工作人员,你能找出谁能最先救美吗(找出一个就行)?(时间只与步骤有关)有时会有很多美女求救,可惜这些工作人员喜欢竞争每次只救一个美女;然后再救下一个。有时迷宫会变,因而可能求救时,可能救不到。当然事先你要进行迷宫处理;美女位置用字符‘2’表示,不能走的地方用字符‘1’表示,能走的则用‘0’表示。处理后称之为 迷宫“012”图 。迷宫最多99行99列

Input

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

Output

对任意不大于99行99列的迷宫;能救到得输出最少步数;不能救到的则输出“Impossible”

Sample Input

2
0101010
1000101
1100010
1001201
1010110
1000001
0100100
#
011111
110201
101011
111111
#

Sample Output

The least step is:2
Impossible

Hint

None

Source

ZhuLi

提交代码