题目描述

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

样例

数据范围
0≤n≤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

算法1

C++ 代码

#include<stdio.h>//本迷宫亮点设置memory数组来记忆曾经走过的路
#include<iostream>
#include<queue>
#define N 1000
using namespace std;
struct Node{
    int x;
    int y;
}node;
struct Node memory[N][N];
int dxy[4][2]={0,1,0,-1,1,0,-1,0};
int map[N][N];
bool st[N][N];
int n;
queue<Node>q;
void shuchu(int x1,int y1){//将其正序输出
    if(memory[x1][y1].x==0&&memory[x1][y1].y==0){
        printf("0 0\n");return;
    } 
    shuchu(memory[x1][y1].x,memory[x1][y1].y);//要先递归   否则会逆序输出
    printf("%d %d\n",memory[x1][y1].x,memory[x1][y1].y);

}
void bfs(){
    q.push({0,0});
    st[0][0]=1;
    while(!q.empty()){
        node=q.front();
        if(node.x==n-1&&node.y==n-1){
            shuchu(node.x,node.y);
            printf("%d %d\n",n-1,n-1);
        }
        q.pop();
        for(int i=0;i<4;i++){
            int xx=node.x+dxy[i][0];
            int yy=node.y+dxy[i][1];
            if(xx<0||xx>=n||yy<0||yy>=n)continue;
            if(st[xx][yy]||map[xx][yy]==1)continue;
            q.push({xx,yy});
            st[xx][yy]=1;
            memory[xx][yy]={node.x,node.y};//继承自哪一个
    }
}
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++) 
        scanf("%d",&map[i][j]);
    bfs(); 

    return 0;
}