300304 - 路径输出

时间限制

20 毫秒

内存限制

128 MB

通过次数

5

提交次数

10

对于神犇而言,一个走迷宫的程序只输出最短步数明显是low的,神犇希望能够输出最短路径。现在有一个550表示通道、1表示墙壁的矩阵地图,输出从左上角达到右下角的最短路线。

输入

共5行,每行有单个空格分隔的5个0或1。

对于100%的数据:

仅存在一条最短路径。

输出

若干行,每行一个(x,y)格式的坐标。具体格式见样例。

样例

输入

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
1 1 0 1 0
0 0 1 1 0

输出

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