labyrinth_1193.cpp (2957B)
1 #include <iostream> 2 #include <queue> 3 #include <ranges> 4 #include <string> 5 #include <tuple> 6 #include <vector> 7 8 struct Pos { 9 size_t i; 10 size_t j; 11 12 Pos(size_t a = 0, size_t b = 0) : i{a}, j{b} {} 13 bool operator==(const Pos& p) const { return i == p.i && j == p.j; } 14 15 std::vector<Pos> neighbors() const { 16 return {Pos(i+1, j), Pos(i-1, j), Pos(i, j+1), Pos(i, j-1)}; 17 } 18 19 char dir(const Pos& p) const { 20 if (p.i == i+1 && p.j == j) return 'D'; 21 if (p.i == i-1 && p.j == j) return 'U'; 22 if (p.i == i && p.j == j+1) return 'R'; 23 if (p.i == i && p.j == j-1) return 'L'; 24 return 'X'; 25 } 26 }; 27 28 class Map { 29 public: 30 Map(size_t i, size_t j) : n{i}, m{j}, v(n, std::vector<bool>(m)) {} 31 Pos start() const { return a; } 32 Pos finish() const { return b; } 33 bool operator[](Pos p) const { return inb(p) && v[p.i][p.j]; } 34 35 friend std::istream& operator>>(std::istream& is, Map& map) { 36 std::string s; 37 is >> s; 38 for (size_t j = 0; j < map.m; j++) 39 map.readchar(s[j], map.l, j); 40 map.l++; 41 return is; 42 } 43 44 friend std::ostream& operator<<(std::ostream& os, const Map& map) { 45 for (size_t i = 0; i < map.n; i++) { 46 for (size_t j = 0; j < map.m; j++) { 47 if (map.a == Pos(i, j)) os << 'A'; 48 else if (map.b == Pos(i, j)) os << 'B'; 49 else os << (map.v[i][j] ? '.' : '#'); 50 } 51 os << "\n"; 52 } 53 return os; 54 } 55 56 template<typename T> 57 using Overlay = std::pair<T, std::vector<std::vector<T>>>; 58 59 template<typename T> 60 Overlay<T> overlay(T t) const { 61 auto ov = std::vector<std::vector<T>>(n, std::vector(m, t)); 62 return {t, ov}; 63 } 64 65 template<typename T> 66 T at(const Overlay<T>& ov, Pos p) const { 67 return inb(p) ? ov.second[p.i][p.j] : ov.first; 68 } 69 70 template<typename T> 71 void set(Overlay<T>& ov, Pos p, T val) const { 72 if (inb(p)) ov.second[p.i][p.j] = val; 73 } 74 private: 75 size_t l{0}; 76 size_t n; 77 size_t m; 78 Pos a; 79 Pos b; 80 std::vector<std::vector<bool>> v; 81 82 void readchar(char c, size_t i, size_t j) { 83 v[i][j] = c != '#'; 84 if (c == 'A') a = {i, j}; 85 if (c == 'B') b = {i, j}; 86 } 87 88 bool inb(Pos p) const { return p.i < n && p.j < m; } 89 }; 90 91 int main() { 92 size_t n, m; 93 std::cin >> n >> m; 94 Map map(n, m); 95 for (size_t i = 0; i < n; i++) 96 std::cin >> map; 97 98 constexpr size_t inf{999999999}; 99 auto d = map.overlay<size_t>(inf); 100 std::queue<std::pair<Pos, size_t>> q; 101 q.push({map.start(), 0}); 102 while (!q.empty()) { 103 auto [p, w] = q.front(); 104 q.pop(); 105 if (!map[p] || map.at(d, p) != inf) continue; 106 map.set(d, p, w); 107 for (auto x : p.neighbors()) q.push({x, w+1}); 108 } 109 110 if (map.at(d, map.finish()) == inf) { 111 std::cout << "NO\n"; 112 } else { 113 std::cout << "YES\n" << map.at(d, map.finish()) << "\n"; 114 115 // Backtrack 116 Pos p = map.finish(); 117 std::vector<char> path; 118 do { 119 for (auto x : p.neighbors()) { 120 if (map.at(d, x) == map.at(d, p)-1) { 121 path.push_back(x.dir(p)); 122 p = x; 123 break; 124 } 125 } 126 } while (p != map.start()); 127 for (auto c : path | std::views::reverse) 128 std::cout << c; 129 std::cout << "\n"; 130 } 131 }