day21a.cpp (2442B)
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 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 int64_t pushes(char c, char d, map<char, 62 pair<int, int>>& m, map<pair<int, int>, char>& r, int n) { 63 auto p = paths(c, d, m, r); 64 auto ret = numeric_limits<int64_t>::max(); 65 for (auto path : p) { 66 if (n == 0) { 67 ret = min(ret, (int64_t)path.size()+1); 68 } else { 69 path = 'A' + path + 'A'; 70 int64_t u = 0; 71 for (unsigned i = 0; i < path.size()-1; i++) 72 u += pushes(path[i], path[i+1], m_dir, rev_dir, n-1); 73 ret = min(ret, u); 74 } 75 } 76 return ret; 77 } 78 79 int64_t numeric(const string& code) { 80 return (code[0]-'0')*100 + (code[1]-'0')*10 + (code[2]-'0'); 81 } 82 83 int main() { 84 for (auto [k, v] : m_num) rev_num[v] = k; 85 for (auto [k, v] : m_dir) rev_dir[v] = k; 86 87 string line; 88 int64_t tot = 0; 89 while (getline(cin, line)) { 90 int64_t comp = 0; 91 int64_t num = numeric(line); 92 line = 'A' + line; 93 for (unsigned i = 0; i < line.size()-1; i++) 94 comp += pushes(line[i], line[i+1], m_num, rev_num, 2); 95 tot += comp * num; 96 } 97 cout << tot << endl; 98 return 0; 99 }