#P1209. 小老鼠走迷宫3

小老鼠走迷宫3

题目描述
一个M*N的迷宫矩阵由 0 和 1 组成,1 表示墙壁,0 表示通路。
一只小老鼠从左上角即坐标(0,0)出发,只能走上下左右四个方向(不能走斜线),问小老鼠最少要走多少步才能到右下角出口即坐标(M-1,N-1)处的奶酪。

输入格式
第一行输入空格分开的两个整数,表示迷宫的行数和列数。
然后输入M行N列的迷宫矩阵。

数据范围
5 <= M,N <= 50

输出格式
先输出小老鼠走到奶酪处的最少步数,如果不能走到右下角则输出**-1**。 如果有路径可以到达奶酪处,则在第二行输出对应的方案。如果有多个方案的步数同为最小值,按照右 > 下 > 左 > 上的优先顺序来输出第一个方案。

样例

5 5
0 0 1 0 1
0 0 1 0 0
0 1 0 1 1
0 1 0 0 0
0 0 0 0 0
8
(0,0)->(1,0)->(2,0)->(3,0)->(4,0)->(4,1)->(4,2)->(4,3)->(4,4)
5 5
0 0 1 0 1
0 0 1 0 0
0 1 0 1 1
0 1 1 0 0
0 0 1 0 0

-1