``` #include <bits/stdc++.h> using namespace std; const int N = 55; int n, m; char g[N][N]; int dx[4] = {1, 0, 0, -1}, dy[4] = {0, -1, 1, 0}; string mp[4] = {"D", "L", "R", "U"}; string ans[N][N]; bool st[N][N]; string bfs() { queue<pair<int, int>> q; q.push({0, 0}); st[0][0] = true; ans[0][0] = ""; while (q.size()) { auto t = q.front(); if (t.first == n - 1 && t.second == m - 1) return ans[t.first][t.second]; q.pop(); for (int i = 0; i < 4; ++i) { int tx = t.first + dx[i], ty = t.second + dy[i]; if (tx >= 0 && tx < n && ty >= 0 && ty < m && g[tx][ty] == '0' && !st[tx][ty]) { st[tx][ty] = true; ans[tx][ty] = ans[t.first][t.second] + mp[i]; q.push({tx, ty}); } } } return ""; } int main() { freopen("input.txt", "r", stdin); n = 30, m = 50; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> g[i][j]; cout << bfs() << endl; return 0; } ```

``` #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<utility> #include<vector> using namespace std; #define x first #define y second int a[30][50] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0 }; int dx[5]={1,0,0,-1},dy[5]={0,-1,1,0};//注意题目上是按照字典序 char dir[5]={'D','L','R','U'}; bool vis[100][100]; queue<int> qx; queue<int> qy; vector<char> v; struct fa{ int fx,fy; char d; }; fa path[30][50]; void bfs(int x,int y) { bool flag=false; qx.push(x); qy.push(y); vis[x][y]=true; while(!qx.empty()&!qy.empty()) { for(int i=0;i<4;i++)//取队头进行扩展 { int tx=qx.front()+dx[i]; int ty=qy.front()+dy[i]; if(a[tx][ty]==1||tx<0||ty<0||tx>29||ty>49||vis[tx][ty])continue; path[tx][ty].fx=qx.front(); path[tx][ty].fy=qy.front(); path[tx][ty].d=dir[i]; if(tx==29&&ty==49) { flag=true; break; } qx.push(tx); qy.push(ty); vis[tx][ty]=true; } qx.pop(); qy.pop(); if(flag)break; } return ; } int main() { bfs(0,0); int x=29,y=49; while(x||y)//不同时为0 即起点 就往前回溯 { auto t=path[x][y];//注意不要 x=path[x][y].fx,y=path[x][y].fy;x第一步被修改了 v.push_back(t.d); x=t.fx; y=t.fy; } reverse(v.begin(),v.end()); for(auto i:v)cout<<i; return 0; } ```

``` #include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int n,m; vector<pii> path[35][55]; // 用于输出路径，和path_dir在后面依次累加想法一致 string path_dir[35][55]; int dx[]={1,0,0,-1}; int dy[]={0,-1,1,0}; char mp[]={'D','L','R','U'}; char g[35][55]; void bfs(){ queue<pii> q; q.push({1,1}); g[1][1]='1'; while(q.size()){ auto t=q.front(); q.pop(); for(int i=0;i<4;i++){ int a=t.first+dx[i],b=t.second+dy[i]; if(g[a][b]=='0'){ q.push({a,b}); g[a][b]='1'; path_dir[a][b]=path_dir[t.first][t.second]+mp[i]; path[a][b]=path[t.first][t.second]; path[a][b].push_back({t.first,t.second}); } } } } int main(){ cin>>n>>m; for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ g[i][j]='1'; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>g[i][j]; } } bfs(); cout<<path_dir[n][m]<<endl; for(auto x:path[n][m]){ cout<<x.first<<" "<<x.second<<endl; } return 0; } //D<L<R<U 下左右上 //DRRURRDDDR //0223220002 ```

``` #include <iostream> #include <queue> #include <algorithm> using namespace std; typedef pair<int,int> pii; int n,m; struct p{ pii pre_point; char predir; }pre[35][55]; string path=""; int dx[]={1,0,0,-1}; int dy[]={0,-1,1,0}; char map[]={'D','L','R','U'}; char g[35][55]; void bfs(){ queue<pii> q; q.push({1,1}); g[1][1]='1'; while(q.size()){ auto t=q.front(); q.pop(); for(int i=0;i<4;i++){ int a=t.first+dx[i],b=t.second+dy[i]; if(g[a][b]=='0'){ q.push({a,b}); g[a][b]='1'; pre[a][b].predir=map[i]; pre[a][b].pre_point=t; } } } } int main(){ cin>>n>>m; for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ g[i][j]='1'; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>g[i][j]; } } bfs(); int a=n,b=m; while(pre[a][b].pre_point!=make_pair(1,1)){ path+=pre[a][b].predir; int tempa=pre[a][b].pre_point.first,tempb=pre[a][b].pre_point.second; a=tempa,b=tempb; //cout<<a<<" "<<b<<endl; } path+=pre[a][b].predir; reverse(path.begin(),path.end()); cout<<path<<endl; return 0; } //D<L<R<U 下左右上 //DRRURRDDDR //0223220002 ```

``` #include<bits/stdc++.h> using namespace std; const int N=55; int n,m; char g[N][N]; int dx[4]={1,0,0,-1}; int dy[4]={0,-1,1,0}; char mp[4]={'D','L','R','U'}; string ans[N][N]; bool st[N][N]; string bfs() { queue<pair<int,int>> q; q.push({0,0}); st[0][0]=true; ans[0][0]=""; while(!q.empty()) { auto t=q.front(); if(t.first==n-1&&t.second==m-1) { return ans[t.first][t.second]; } q.pop(); for(int i=0;i<4;i++) { int tx=t.first+dx[i],ty=t.second+dy[i]; if(tx>=0&&tx<n&&ty>=0&&ty<m&&g[tx][ty]=='0'&&!st[tx][ty]) { st[tx][ty]=true; ans[tx][ty]=ans[t.first][t.second]+mp[i]; q.push({tx,ty}); } } } return ""; } int main() { n=30,m=50; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>g[i][j]; } } cout<<bfs(); return 0; } ```

python ``` from collections import deque vis = [[False]*(55) for _ in range(35)] m,n = map(int,input().split()) a = [] for i in range(m): a.append(list(map(int,input()))) #方向的代表字母为D/R/U/L dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] res = [[""]*55 for _ in range(35)] res[0][0] = "" keys = [['U'],['R'],['D'],['L']] def bfs(i,j): q = deque() q.append((i,j)) while q: x,y = q.popleft() if vis[x][y] : continue vis[x][y] = True if x==m-1 and y==n-1: print(*res[m-1][n-1],sep="") return for k in range(4): xx,yy = x+dx[k],y+dy[k] res.append(keys[k]) if xx<0 or xx>m-1 or yy<0 or yy>n-1 or a[xx][yy]== 1: continue res[xx][yy] = list(res[x][y])+keys[k] q.append((xx,yy)) bfs(0,0) ```

``` #include <bits/stdc++.h> using namespace std; char g[31][51]; int sh[31][51]; string processStr[31][51]; const int dx[] = {1, 0, 0, -1}; const int dy[] = {0, -1, 1, 0}; char addStr(int i) { if (i == 0) return 'D'; else if (i == 1) return 'L'; else if (i == 2) return 'R'; else if (i == 3) return 'U'; return 'e'; } void bfs() { memset(sh, -1, sizeof sh); sh[1][1] = 0; queue<pair<int, int>> q; q.push({1, 1}); processStr[1][1] = ""; while (q.size()) { auto t = q.front(); q.pop(); for (int i = 0; i < 4; i ++) { auto x = t.first + dx[i]; auto y = t.second + dy[i]; if (x < 1 || x > 30 || y < 1 || y > 50 || g[x][y] == '1' || sh[x][y] != -1) continue; sh[x][y] = sh[t.first][t.second] + 1; processStr[x][y] = processStr[t.first][t.second] + addStr(i); q.push({x, y}); } } } int main(void) { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int x_, y_; cin >> x_ >> y_; for (int i = 1; i <= x_; i ++) { for (int j = 1; j <= y_; j ++) { cin >> g[i][j]; } } bfs(); cout << sh[x_][y_] << endl; cout << processStr[x_][y_]; } ```