解题思路

有一个 n * m 大小的01迷宫，0表示这个位置可以走，1表示有障碍物不能走。现在需要从起点 (1,1) 走到终点 (n,m)。
如果可以走到终点，求出走的最少步数，并记录如何走到终点的。
如果有多条路径步数一样，选择走字典序最小的那条。
数据保证起点和终点都是 0。

使用 BFS 算法，并将方向按照字典序排序，这样保证路径的字典序最小。
令使用 pre 记录到达点 (a,b) 的前一个点 (x,y)，这样可以从终点到起点还原路线。

C++代码

#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;

int d[4][2] = {{1,0}, {0,-1}, {0,1}, {-1,0}};
string sd = "DLRU";

map<pair<int,int>, pair<int,int>> pre;

int bfs(vector<vector<char>>& ground){
    int n = ground.size();
    int m = ground[0].size();
    int len = 1;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    visited[0][0] = true;
    queue<pair<int,int>> que;
    que.push(make_pair(0,0));
    int cnt = que.size();
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        for(int i=0; i<4; ++i){
            int a = x + d[i][0];
            int b = y + d[i][1];
            if(a>=0 && a<n && b>=0 && b<m && ground[a][b]=='0' && visited[a][b]==false){
                pre[make_pair(a,b)] = make_pair(x,y);
                visited[a][b] = true;
                que.push(make_pair(a,b));
                if(a==n-1 && b==m-1){
                    return len;
                }
            }
        }
        --cnt;
        if(cnt == 0){
            ++len;
            cnt = que.size();
        }
    }
    return -1;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<char>> ground(n, vector<char>(m));
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j)
            cin >> ground[i][j];
    }
    int len = bfs(ground);
    cout << len << endl;
    if(len != -1){
        string ans = "";
        int a = n-1;
        int b = m-1;
        auto p = make_pair(a,b);
        while(pre.find(p) != pre.end()){
            int x = pre[p].first;
            int y = pre[p].second;
            for(int i=0; i<4; ++i){
                if(a-x==d[i][0] && b-y==d[i][1])
                    ans = sd[i] + ans;
            }
            a = x;
            b = y;
            p = make_pair(a,b);
        }
        cout << ans << endl;
    }
    return 0;
}