1580: 迷宫最短路径
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：146
解决：128
题目描述
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。要求求出从入口（1，1）到出口（m,n）的一条最短通路。如果有多条最短通路，则优先输出靠下、靠左的通路。即，迷宫中选择方向时按照左、下、右、上的顺序进行。
例如，如下迷宫中：
从（1,1）到（5,7）的最短通路有2条：
（1,1）（2,1）（2,2）（2,3）（2,4）（3,4）（3,5）（3,6）（4,6）（5,6）（5,7）
（1,1）（2,1）（2,2）（2,3）（2,4）（2,5）（2,6）（3,6）（4,6）（5,6）（5,7）
则按照方向顺序输出的是：
（1,1）（2,1）（2,2）（2,3）（2,4）（3,4）（3,5）（3,6）（4,6）（5,6）（5,7）
输入
输入有若干个案例，每个案例的第1行有两个整数m、n，分别表示迷宫的行数和列数。m=n=0表示结束。接着有m行n列的0或者1，1表示墙。
输出
输出从左上角（1,1）的入口到右下角（m,n）的出口的最短通路。
样例输入 复制
5 7
0111111
0000001
1010001
1000101
1010100
样例输出 复制
(1,1)(2,1)(2,2)(2,3)(2,4)(3,4)(3,5)(3,6)(4,6)(5,6)(5,7)