AcWing 1076. 迷宫问题

题目传送门

一、本题学习目的

练习使用广度优先搜索时，记录路径的办法，可以采用倒序的广度优先搜索，也可以采用正序的广度优先搜索，但倒序的代码简单些，正序的麻烦些。

二、倒序

#include 

using namespace std;

//边权为1的时候，可以使用bfs求最短路径
//学习：bfs中如何记录路径，就是把bool st[N][N]修改为pair类型，记录前序是哪个点
//这样,st就不光可以记录走没走过(没走过的话，值为空，走过的话有PII值)，而且可以通过PII反推回走的路线
#define x first
#define y second
typedef pair PII;
const int N = 1010, M = N * N;
int n;
int g[N][N];              //地图
PII q[M];                 //队列
PII pre[N][N];            //前序坐标
int dx[] = {-1, 0, 1, 0}; //上右下左
int dy[] = {0, 1, 0, -1}; //上右下左

// bfs的特点决定它第一次找到的出口点，就是最短路径
void bfs(int sx, int sy) {
    //将起始点初始化到队列中
    int hh = 0, tt = -1;
    q[++tt] = {sx, sy};

    //初始化一个不存在的值,用以区分是不是走过了
    memset(pre, -1, sizeof pre);
    pre[sx][sy] = {0, 0}; //最后一个位置(n-1,n-1)只要设置一个非-1的值，就描述它走过了，防止重复走

    while (hh <= tt) {
        PII t = q[hh++];
        for (int i = 0; i < 4; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= n) continue; //不越界
            if (g[a][b]) continue;                            //是墙
            if (pre[a][b].x != -1) continue;                  //走过
            //可以走
            q[++tt] = {a, b}; //将可以走的点入队列
            pre[a][b] = t;    //记录从t可以走到{a,b}
        }
    }
}
int main() {
    //优化读入
    ios::sync_with_stdio(false);
    cin >> n;
    //本题要求左上角是(0,0)，下标不能从1开始
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];

    //因为每个节点都记录的是自己的上一步是谁，但没有记录自己的下一步是谁
    //所以，如果是正向搜索，从(0,0)出发，(0,0)不知道自己的下一步是哪个位置！

    //如果倒着搜索，从(n-1,n-1)出发，则遍历到的每个位置坐标(x,y),都知道自己的前序是谁，
    //一直到(0,0),(0,0)也就知道了自己的前序节点是哪个,这是一个通用的套路
    bfs(n - 1, n - 1);

    //输出路径
    PII start = {0, 0};
    while (true) {
        printf("%d %d\n", start.x, start.y);
        if (start.x == n - 1 && start.y == n - 1) break;
        start = pre[start.x][start.y];
    }
    return 0;
}

三、正序

#include 

using namespace std;

//边权为1的时候，可以使用bfs求最短路径
//学习：bfs中如何记录路径，就是把bool st[N][N]修改为pair类型，记录前序是哪个点
//这样,st就不光可以记录走没走过(没走过的话，值为空，走过的话有PII值)，而且可以通过PII反推回走的路线
#define x first
#define y second
typedef pair PII;
const int N = 1010, M = N * N;
int n;
int g[N][N];              //地图
PII q[M];                 //队列
PII pre[N][N];            //前序坐标
int dx[] = {-1, 0, 1, 0}; //上右下左
int dy[] = {0, 1, 0, -1}; //上右下左

void bfs(int sx, int sy) {
    //将起始点初始化到队列中
    int hh = 0, tt = -1;
    q[++tt] = {sx, sy};

    //初始化一个不存在的值,用以区分是不是走过了
    memset(pre, -1, sizeof pre);
    pre[sx][sy] = {0, 0}; //最后一个位置(n-1,n-1)只要设置一个非-1的值，就描述它走过了，防止重复走

    while (hh <= tt) {
        PII t = q[hh++];
        for (int i = 0; i < 4; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= n) continue; //不越界
            if (g[a][b]) continue;                            //是墙
            if (pre[a][b].x != -1) continue;                  //走过
            //可以走
            q[++tt] = {a, b}; //下一个要检查的坐标
            pre[a][b] = t;    //从t可以走到{a,b}
        }
    }
}
int main() {
    //优化读入
    ios::sync_with_stdio(false);
    cin >> n;
    //本题要求左上角是(0,0)，下标不能从1开始
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];

    //正着搜索
    bfs(0, 0);

    //输出路径
    vector path;
    PII start = {n - 1, n - 1};
    path.push_back(start);
    while (true) {
        if (start.x == 0 && start.y == 0) break;
        start = pre[start.x][start.y];
        path.push_back(start);
    }
    for (int i = path.size() - 1; i >= 0; i--)
        printf("%d %d\n", path[i].x, path[i].y);
    return 0;
}