摘要
Title: HJ43 迷宫问题
Tag: BFS
Memory Limit: 64 MB
Time Limit: 1000 ms

HJ43 迷宫问题

题意

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路
思路

由于BFS只走一遍的特性，可以直接构建一个单向链表记录路径

代码

#include <algorithm>
#include <bits/stdc++.h>
#include <cctype>
#include <cstdio>
#include <queue>
#include <sstream>
#include <vector>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'

const int N = 30, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;

int g[N][N];
int st[N][N];


struct sa {
    int x, y;
};


sa vis[N][N];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

signed main() {
    // freopen("Tests/input_1.txt", "r", stdin);
    IOS;

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) cin >> g[i][j];
    queue<sa> q;

    int sx = 1, sy = 1;
    q.push({sx, sy});
    vis[sx][sy] = {-1, -1};
    st[sx][sy] = 1;

    auto solve = [&] (sa t) {

        vector <sa> ans;
        while (t.x != -1) {
            ans.push_back({t.x, t.y});
            t = vis[t.x][t.y];
        }
        reverse(ans.begin(), ans.end());
        for (auto t : ans) {
            printf("(%d,%d)\n", t.x - 1, t.y - 1);
        }
    };

    while (SZ(q)) {

        auto t = q.front();
        q.pop();

        if (t.x == n && t.y == m) {
            solve(t);
            break;
        }
        for (int i = 0; i < 4; ++i) {
            int x = t.x + dir[i][0];
            int y = t.y + dir[i][1];
            if (x >= 1 && x <= n && y >= 1 && y <= m && !st[x][y] && !g[x][y]) {
                q.push({x, y});
                vis[x][y] = {t.x, t.y};
                st[x][y] = 1;
            }
        }

    }

    return 0;
}

HJ43 迷宫问题

题意

思路

代码