题解 | 牛牛走迷宫 | 从终点开始BFS，从起点走最小字典序下降阶梯喵

#include <bits/stdc++.h>
using namespace std;

const int N = 505, inf = 1e9;
const int dir[] = {1,0,-1,0,1};

int n, m;
int d[N][N];
char mat[N][N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
            d[i][j] = inf;
        } 
    d[n][m] = 0;
    queue<array<int, 2>> Q;
    Q.push({n, m});
    while (Q.size()) {
        auto [x, y] = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i], ny = y + dir[i+1];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <=m && d[nx][ny] == inf && mat[nx][ny] == '0') {
                d[nx][ny] = d[x][y] + 1;
                Q.push({nx, ny});
            }
        }
    }
    if (d[1][1] == inf) {
        cout << -1 << "\n";
        return;
    }
    int x = 1, y = 1;
    string path;
    while(x!=n||y!=m) {
        if(x < n && d[x+1][y] == d[x][y] - 1) x++, path.push_back('D');
        else if(y > 1 && d[x][y-1] == d[x][y] - 1) y--, path.push_back('L');
        else if(y < m && d[x][y+1] == d[x][y] - 1) y++, path.push_back('R');
        else if(x > 1 && d[x-1][y] == d[x][y] - 1) x--, path.push_back('U');
    }
    cout << path.size() << "\n";
    cout << path << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    while (T--) solve();
}
// 64 位输出请用 printf("%lld")