牛客小白月赛26 E 牛牛走迷宫

Description

牛牛周末去了游乐园走迷宫。这是一个n*m大小的01迷宫，0表示这个位置可以走，1表示有障碍物不能。
走。现在牛牛在起点(1,1),他想要走到终点(n,m)。并且，如果他能够走到终点的话，他想要知道自己是怎么走到终点的。
如果可以走到终点，因为牛牛比较懒他会先保证走的步数最少，又因为牛牛是个追求完美的人，如果有多
条路径步数一样，他会选择走字典序最小的那条。
数据保证起点和终点都是0

Solution

最短路+字典序最小，非常经典的bfs题目，值得注意的是我们bfs的时候顺序应该按照题意要求的，
分别是DLRU去做，这样最先到达终点的点一定是最短且字典序最小的。
因此只需要做一遍bfs即可。

Code

#include<bits/stdc++.h>
typedef long long ll;
const int N = 1e6 + 5;
using namespace std;
char maze[505][505];
struct node {
  int x, y;
  int step;
  string ans;
  node(int _x = 0, int _y = 0, int _step = 0, string _ans = ""): x(_x), y(_y), step(_step), ans(_ans){}
};
int n, m;
bool vis[505][505];
int dist[4][2] = {1, 0, 0, -1, 0, 1, -1, 0};
string p = "DLRU";
void bfs(int x, int y) {
  queue<node> q;
  q.push(node(x, y, 0, ""));
  vis[x][y] = 1;
  while(!q.empty()) {
    node now = q.front();
    q.pop();
    //cout << now.x << ' ' << now.y << "\n";
    if(now.x == n && now.y == m) {
      cout << now.step << "\n";
      cout << now.ans << "\n";
      return ;
    }
    for(int i = 0; i < 4; i++) {
      int xx = now.x + dist[i][0];
      int yy = now.y + dist[i][1];
      //cout << xx << ' ' << yy << "\n";
      if(!vis[xx][yy] && maze[xx][yy] == '0' && xx <= n && xx >= 1 && yy >= 1 && yy <= m) {
        vis[xx][yy] = 1;
        q.push(node(xx, yy, now.step + 1, now.ans + p[i]));
      }
    }
  }
  cout << -1 << "\n";
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++)  cin >> maze[i][j];
  }
  bfs(1, 1);
  return 0;
}