题目描述

给定一个 n×n 的二维数组，如下所示：

int maze[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,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 数据保证至少只存在一条从左上角走到右下角的路径。

输入

第一行包含整数 n。 接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。

输出

输出从左上角到右下角的最短路线。 按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。

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

提示

$0≤n≤1000$