题目描述

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

(暴力枚举) $O(n^2)$

迷宫问题是我第一次学BFS遇到的问题~。~，太经典了，注意点就是最短路求具体路径时（dijkstra求最短路径的具体路径时同样适用~。~），只能记录入度，因为最短路的出度很多，但是入度是唯一的。

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

#define pii pair<int,int>

using namespace std;

const int N = 1010 , M = N * N;

int g[N][N],dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

bool st[N][N];

int n;

pii pre[N][N],q[M];

void bfs(int x,int y)
{
    st[x][y] = true;

    int tt=0,hh=0;

    pre[x][y]={-1,-1};

    q[0]={x,y};

    while(hh<=tt)
    {
        auto t=q[hh++];
        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a>=0&&a<n&&b>=0&&b<n&&!st[a][b]&&!g[a][b])
            {
                st[a][b]=true;
                q[++tt]={a,b};
                pre[a][b]={t.first,t.second};
            }
        }

    }

}
int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    scanf("%d",&n);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&g[i][j]);

    bfs(0,0);

    vector<pii> res;

    pii end={n-1,n-1};

    while(end!=make_pair(-1,-1))
    {
        res.push_back(end);
        end=pre[end.first][end.second];
    }

    for(auto it = res.rbegin();it != res.rend();it++)
        printf("%d %d\n",it->first,it->second);

    return 0;
}