题目描述

给定一个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。

注：答案不唯一，课上程序可通过。广度优先，上右下左顺序遍历。

C++视频链接