grid_path_description_1625.cpp (3241B)
1 #include <algorithm> 2 #include <bitset> 3 #include <iostream> 4 #include <queue> 5 #include <string> 6 #include <vector> 7 8 /* 9 The official solution uses the heuristic: if both adjacent squares 10 in horizontal direction are visited or wall, and both in vertical direction 11 are not visited (or the other way round), then we stop because we borked 12 the square. I did not think of this criterion, so to check if the square 13 is borked I do a full visit from the bottom-left corner. This is too slow, 14 so I do this only at depths 10, 20, 30 and 40. This is good enough. 15 */ 16 17 class Tile { 18 public: 19 int i; 20 int j; 21 22 bool valid() const { return i >= 0 && i < 7 && j >= 0 && j < 7; } 23 bool end() const { return i == 6 && j == 0; } 24 bool operator==(const Tile& t) const { return i == t.i && j == t.j; } 25 Tile u() const { return Tile{i-1, j}; } 26 Tile d() const { return Tile{i+1, j}; } 27 Tile l() const { return Tile{i, j-1}; } 28 Tile r() const { return Tile{i, j+1}; } 29 static Tile err() { return Tile{-1, -1}; } 30 31 Tile move(char c) const { 32 if (c == 'U') return u(); 33 if (c == 'D') return d(); 34 if (c == 'L') return l(); 35 if (c == 'R') return r(); 36 return err(); 37 } 38 39 std::vector<Tile> neighbors() const { 40 return std::vector { u(), d(), l(), r() }; 41 } 42 }; 43 44 class Map { 45 public: 46 Map() : b(), v(49, 4) { 47 for (int i = 0; i < 7; i++) { 48 v[index(Tile{i, 0})]--; 49 v[index(Tile{i, 6})]--; 50 v[index(Tile{0, i})]--; 51 v[index(Tile{6, i})]--; 52 } 53 } 54 55 bool visited(Tile t) const { 56 return !t.valid() || b.test(index(t)); 57 } 58 59 void set(Tile t) { 60 if (!t.valid()) return; 61 b.set(index(t)); 62 for (auto u : t.neighbors()) 63 if (u.valid()) 64 v[index(u)]--; 65 } 66 67 void reset(Tile t) { 68 if (!t.valid()) return; 69 b.reset(index(t)); 70 for (auto u : t.neighbors()) 71 if (u.valid()) 72 v[index(u)]++; 73 } 74 75 std::vector<Tile> locked_neighbors(Tile t) const { 76 std::vector<Tile> r{}; 77 for (auto u : t.neighbors()) 78 if (locked(u)) 79 r.push_back(u); 80 return r; 81 } 82 83 int count() const { return b.count(); } 84 85 bool borked() const { 86 std::bitset<49> vv{}; 87 std::queue<Tile> q; 88 q.push(Tile{6, 0}); 89 vv.set(index(Tile{6, 0})); 90 int c{1}; 91 while (!q.empty()) { 92 Tile t = q.front(); 93 q.pop(); 94 for (auto u : t.neighbors()) { 95 if (!visited(u) && !vv.test(index(u))) { 96 vv.set(index(u)); 97 c++; 98 q.push(u); 99 } 100 } 101 } 102 103 return c + count() < 49; 104 } 105 106 private: 107 std::bitset<49> b; 108 std::vector<int> v; 109 static int index(Tile t) { return 7*t.i + t.j; } 110 111 bool locked(Tile t) const { 112 return t.valid() && !visited(t) && !t.end() && v[index(t)] < 2; 113 } 114 }; 115 116 int f(Map& m, const std::string& s, size_t n, Tile t) { 117 if (n == 48) return t.end(); 118 if (m.visited(t) || t.end()) return 0; 119 120 m.set(t); 121 if (n % 10 == 0 && m.borked()) { 122 m.reset(t); 123 return 0; 124 } 125 126 auto ln = m.locked_neighbors(t); 127 128 int r{0}; 129 if (s[n] != '?') { 130 Tile nt = t.move(s[n]); 131 if (ln.size() == 0 || (ln.size() == 1 && ln[0] == nt)) 132 r = f(m, s, n+1, nt); 133 } else { 134 if (ln.size() == 0) 135 r = f(m, s, n+1, t.u()) + f(m, s, n+1, t.d()) 136 + f(m, s, n+1, t.l()) + f(m, s, n+1, t.r()); 137 if (ln.size() == 1) 138 r = f(m, s, n+1, ln[0]); 139 } 140 141 m.reset(t); 142 return r; 143 } 144 145 int main() { 146 Map m; 147 std::string s; 148 std::cin >> s; 149 std::cout << f(m, s, 0, Tile{0, 0}) << "\n"; 150 }