题解 | 牛牛走迷宫

按照题目要求顺序bfs遍历，使用map存当前点从哪个节点过来的，得到的路径字符串反转后就是正向路径

#include <iostream>
#include <type_traits>
#include<vector>
#include<queue>
#include<array>
#include<unordered_map>
#include<algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<char>> vc(n, vector<char>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin>>vc[i][j];
        }
    }

    array<array<int, 2>, 4> dir{{{1, 0}, {0, -1}, {0, 1}, {-1, 0}}};
    vector<vector<int>> visited(n, vector<int> (m, 0));
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = 1;
    array<char, 4> arr{'D', 'L', 'R', 'U'};
    unordered_map<int, pair<int, int>> um;
    string res;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == n - 1 && y == m - 1) {
            // string res;
            int xy = (x << 16) + y;
            while (um.count(xy)) {
                auto [px, py] = um[xy];
                // cout << px << " "<< py << endl;
                if (px + 1 == x) {
                    res.push_back('D');
                } else if (py + 1 == y) {
                    res.push_back('R');
                } else if (px - 1 == x) {
                    res.push_back('U');
                } else if (py - 1 == y){
                    res.push_back('L');
                }
                xy = (px<<16) + py;
                x = px;
                y = py;
            }
            reverse(res.begin(), res.end());
            cout << res.length() << '\n'<<res <<"\n";
            break;
        }
        for (int i = 0; i < 4; i++) {
            int newx = x + dir[i][0];
            int newy = y + dir[i][1];
            if (newx < 0 || newx >= n || newy < 0 || newy >= m || vc[newx][newy]== '1' || visited[newx][newy]) {
                continue;
            }
            q.push({newx, newy});
            visited[newx][newy] = 1;
            // cout << newx << " " << newy << " " << vc[newx][newy]<< endl;
            int idx = (newx<<16) + newy;
            um[idx] = {x, y};
        }
    }
    if (res.length() == 0) {
        cout << -1 << '\n';
    }
    return 0;
}