题目描述

1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线

输入样例

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

正序BFS, 逆序（栈）打印路径

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

using namespace std;

typedef pair<int, int> PII;

#define x first
#define y second

const int N = 1010;

PII pre[N][N];
int n;
int g[N][N];
bool st[N][N];

void bfs()
{
    queue<PII> q;

    q.push({0, 0});
    st[0][0] = true;

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

    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] && !st[x][y])
            {
                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 x1 = n - 1, y1 = n - 1;
    while(x1 || y1){
        s.push({x1, y1});
        auto t = pre[x1][y1];
        x1 = t.x, y1 = t.y;
    }
    s.push({0, 0});

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

    return 0;
}

算法2

逆序BFS, 正序打印

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

PII pre[N][N];
int n;
int g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

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.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < n && !st[x][y] &&  !g[x][y])
            {
                st[x][y] = true;
                q.push({x, y});
                pre[x][y] = t;
            }
        }

    }

    int x = 0, y = 0;
    while (x != n - 1 || y != n - 1)
    {
        cout << x << ' ' << y << endl;
        //cout << '(' << x << ',' << y << ')' << endl;
        auto t = pre[x][y];
        x = t.first, y = t.second;
    }
    //cout << '(' << n - 1 << ',' << n - 1 << ')' << endl;
    cout << n - 1 << ' ' << n - 1 << endl;
}

int main()
{
    scanf("%d", &n);

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

    bfs();

    return 0;
}