题目描述

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

思想：

从(0, 0)向(n - 1, n - 1)搜索可以等价为从(n - 1, n - 1)向(0, 0)搜索.   
我们不妨从(n - 1, n - 1)向(0, 0)搜索.    那这样做有何优势？
在搜索的过程中，我们很容易记下当前位置的前驱,下标n - 1必然是下标n - 1 到0之间某个位置的前驱,n - 2 也必然
是n - 2 到0之间某个位置的下标的前驱,依次类推···打印的时候,我们逆序打印,打印完(0,0)后,再打印他的前驱位置,
以此类推···那么当我们逆序打印(0,0) 到 (n - 1, n - 1)之间记录的下标时,便是由(0,0)到(n - 1, n - 1)的路径.

C++ 代码1 ----- 逆序搜索,正序打印

#include <iostream>
#include <string>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int ,int> PII;

const int N = 1000;

PII pre[N][N];//存储当前位置的前驱
int g[N][N];
bool st[N][N];//表示当前位置的状态，若已用则为true,反之为false.
int n;
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};//当前位置的上、下、左、右偏移量

//从(n - 1, n - 1)向(0, 0)搜寻    ----- 便于方案的打印(可理解为前者元素为后续元素的前驱)
void bfs(){
    queue <PII> q;
    q.push({n - 1, n - 1});
    st[n - 1][n - 1] = true;

    while(q.size()){
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++){
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0 && st[x][y] == false){
                st[x][y] = true;
                q.push({x, y});
                pre[x][y] = t;//存储一下当前合理位置的前驱,即该位置由哪个位置引入
            }
        }
    }

    //打印方案 
    int x = 0, y = 0;
    while(x != n - 1 || y != n - 1){//当x = y = n - 1时,循环截止,因为下标n - 1为第一个元素，它没有前驱
        cout << x << ' ' << y << endl;
        auto t = pre[x][y];
        x = t.x, y = t.y;
    }
    cout << n - 1 << ' ' << n - 1 << endl;//单独打印第一个元素的下标

}

int main(){
    cin >> n;

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            cin >> g[i][j];
        }
    }

    bfs();

    return 0;
}

C ++ 代码2 ----- 正序搜索,正序打印

#include <iostream>
#include <cstring>
#include <queue>
#include <stack>

#define x first
#define y second

using namespace std;

typedef pair<int ,int> PII;

const int N = 1010;

PII pre[N][N];//存储当前位置的前驱
int g[N][N];
bool st[N][N];//表示当前位置的状态，若已用则为true,反之为false.
int n;
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};//当前位置的上、下、左、右偏移量

void bfs(){
    queue <PII> q;

    q.push({0, 0});

    while(q.size()){
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++){
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0 && st[x][y] == false){
                st[x][y] = true;
                pre[x][y] = t;//存储一下当前合理位置的前驱,即该位置由哪个位置引入
                q.push({x, y});
            }
        }
    }
}

int main(){
    cin >> n;

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            cin >> g[i][j];
        }
    }

    bfs();


    stack<PII> s;
    int x = n - 1, y = n - 1;
    while(x || y){
        s.push({x, y});
        auto t = pre[x][y];
        x = t.x, y = t.y;
    }
    s.push({0, 0});

    //打印方案
    while(s.size()){
        PII t = s.top(); s.pop();
        cout << t.x << ' ' << t.y << endl;
    }

    return 0;
}