1076

1076. 迷宫问题

题目

给定一个 $n \times 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)$。

数据范围

$0 \le n \le 1000$

输入样例：

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

题解