day21b.cpp (2590B)
1 #include <algorithm> 2 #include <cstdint> 3 #include <iostream> 4 #include <limits> 5 #include <map> 6 #include <queue> 7 #include <ranges> 8 #include <set> 9 #include <sstream> 10 #include <string> 11 #include <string_view> 12 #include <vector> 13 using namespace std; 14 15 map<char, pair<int, int>> m_num = { 16 {'7', {0,0}}, {'8', {0,1}}, {'9', {0,2}}, 17 {'4', {1,0}}, {'5', {1,1}}, {'6', {1,2}}, 18 {'1', {2,0}}, {'2', {2,1}}, {'3', {2,2}}, 19 {'x', {3,0}}, {'0', {3,1}}, {'A', {3,2}}, 20 }; 21 22 map<char, pair<int, int>> m_dir = { 23 {'x', {0,0}}, {'^', {0,1}}, {'A', {0,2}}, 24 {'<', {1,0}}, {'v', {1,1}}, {'>', {1,2}}, 25 }; 26 27 map<pair<int, int>, char> rev_num; 28 map<pair<int, int>, char> rev_dir; 29 30 map<pair<char, char>, vector<string>> p; 31 32 vector<pair<pair<int, int>, char>> directions = { 33 {{1,0}, 'v'}, {{-1,0}, '^'}, {{0,1}, '>'}, {{0,-1}, '<'} 34 }; 35 36 int distance(int cx, int cy, int dx, int dy) { 37 return abs(cx-dx) + abs(cy-dy); 38 } 39 40 vector<string> paths(char c, char d, 41 map<char, pair<int, int>>& m, map<pair<int, int>, char>& rev) { 42 if (p[make_pair(c, d)].size() != 0) return p[make_pair(c, d)]; 43 if (c == d) return {""}; 44 if (c == 'x') return {}; 45 46 vector<string> v; 47 auto [cx, cy] = m[c]; 48 auto [dx, dy] = m[d]; 49 for (auto [dir, dirc] : directions) { 50 pair i = make_pair(cx+dir.first, cy+dir.second); 51 if (distance(cx, cy, dx, dy) < distance(i.first, i.second, dx, dy)) 52 continue; 53 const auto next = paths(rev[i], d, m, rev); 54 for (auto n : next) 55 v.push_back(dirc+n); 56 } 57 58 return p[make_pair(c, d)] = v; 59 } 60 61 map<tuple<char, char, int>, int64_t> t; 62 int64_t pushes(char c, char d, 63 map<char, pair<int, int>>& m, map<pair<int, int>, char>& r, int n) { 64 if (t.count(make_tuple(c, d, n))) 65 return t[make_tuple(c, d, n)]; 66 const auto p = paths(c, d, m, r); 67 auto ret = numeric_limits<int64_t>::max(); 68 for (const auto& path : p) { 69 if (n == 0) { 70 ret = min(ret, (int64_t)path.size()+1); 71 } else { 72 string q = 'A' + path + 'A'; 73 int64_t u = 0; 74 for (unsigned i = 0; i < q.size()-1; i++) 75 u += pushes(q[i], q[i+1], m_dir, rev_dir, n-1); 76 ret = min(ret, u); 77 } 78 } 79 return t[make_tuple(c, d, n)] = ret; 80 } 81 82 int64_t numeric(const string& code) { 83 return (code[0]-'0')*100 + (code[1]-'0')*10 + (code[2]-'0'); 84 } 85 86 int main() { 87 for (auto [k, v] : m_num) rev_num[v] = k; 88 for (auto [k, v] : m_dir) rev_dir[v] = k; 89 90 string line; 91 int64_t tot = 0; 92 while (getline(cin, line)) { 93 int64_t comp = 0; 94 int64_t num = numeric(line); 95 line = 'A' + line; 96 for (unsigned i = 0; i < line.size()-1; i++) 97 comp += pushes(line[i], line[i+1], m_num, rev_num, 25); 98 tot += comp * num; 99 } 100 cout << tot << endl; 101 return 0; 102 }