有一个 行 列的网格,我们使用 表示网格中从上往下数第 行和从左往右数第 列的单元格。每个方格要么是可以通过的空方格 ,要么是不可通过的墙方格 ,特别的,网格的四周都是墙方格,你可以沿着空方格上下左右随意移动:从 向上移动一格即抵达 、向下移动一格即抵达 、向左移动一格即抵达 、向右移动一格即抵达 。 现在,你位于迷宫的入口 ,想要前往终点 。请输出一条从起点到终点的可行路径。 保证起点和终点一定为空方格,你始终可以找到且能唯一找到一条从起点出发到达终点的可行路径。
输入描述:
第一行输入两个整数 代表迷宫的行数和列数。此后 行,第 行输入 个整数 代表迷宫的布局。其中, 表示单元格 是空方格, 表示单元格 是墙方格。


输出描述:
输出若干行,第 行输出两个整数 ,表示路径的第 步抵达的单元格坐标为 。你需要保证输出的路径是符合题目要求的,即从起点 出发,到达终点 ,且路径上每个单元格都是空方格,行走的单元格都是彼此相邻的。
示例1

输入

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
示例2

输入

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

输出

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
加载中...