题目描述

给定一个 R 行 C 列的迷宫，迷宫中每个位置用数字 1 或 0 表示：其中 1 代表墙壁，无法通行；0 代表可通行的道路。现规定只能沿着水平方向（左右）或垂直方向（上下）移动，不允许斜向移动。 请编写程序，找出从迷宫左上角到右下角的最短路线。

输入描述

第一行包含两个正整数 R 和 C，分别表示迷宫的行数和列数。 接下来 R 行，每行包含 C 个正整数（仅为 0 或 1），表示迷宫的具体布局。数据保证迷宫存在从左上角到右下角的唯一最短路径。

输出描述

左上角到右下角的最短路径，格式如样例所示。

样例数据1

输入

5 5
0 1 0 0 0
0 1 0 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)

数据说明

时间限制：1000ms、内存限制：64MB