题解 | 牛牛走迷宫

Modern Cpp

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <queue>
#include <map>
#include <tuple>
#include <algorithm>

constexpr int inf = 1E9;
constexpr std::array dx = {1, 0, 0, -1};
constexpr std::array dy = {0, -1, 1, 0};
std::string map = "DLRU";

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n, m;
  std::cin >> n >> m;

  std::vector<std::string> g(n);
  for(int i = 0; i < n; i++){
    std::cin >> g[i];
  }

  std::vector dist(n, std::vector<int>(m, inf));
  std::string ans;
  auto bfs = [&](){
    using Node = std::array<int, 2>;
    std::vector vis(n, std::vector<bool>(m));
    std::queue<Node> q;
    std::map<Node, std::tuple<int, int, char>> prev;

    vis[0][0] = true;
    dist[0][0] = 0;
    q.push({0, 0});

    while(q.size()){
      auto [x, y] = q.front();
      q.pop();

      for(int i = 0; i < dx.size(); i++){
        int u = x + dx[i], v = y + dy[i];
        if(u < 0 || u >= n || v < 0 || v >= m || vis[u][v] || g[u][v] == '1'){
          continue;
        }

        vis[u][v] = true;
        dist[u][v] = dist[x][y] + 1;
        prev[{u, v}] = {x, y, map[i]};
        q.push({u, v});
      }
    }

    if(dist[n - 1][m - 1] == inf){
      return;
    }

    int curx = n - 1, cury = m - 1;
    while(curx || cury){
      auto [prevx, prevy, dir] = prev[{curx, cury}];
      ans.push_back(dir);
      curx = prevx;
      cury = prevy;
    }

    std::reverse(ans.begin(), ans.end());
  };

  bfs();

  if(dist[n - 1][m - 1] == inf){
    std::cout << "-1\n";
    return 0;
  }

  std::cout << dist[n - 1][m - 1] << "\n" << ans << "\n";

  return 0;
}