day18b.cpp (1413B)
1 /* 2 I just look the shortest path after every byte drop and stop when there 3 is none. This code is not very fast (~25 seconds on my laptop), but it 4 took just a couple of minutes to modify part 1 to get this. 5 */ 6 7 #include <algorithm> 8 #include <cstdint> 9 #include <iostream> 10 #include <map> 11 #include <queue> 12 #include <ranges> 13 #include <set> 14 #include <sstream> 15 #include <string> 16 #include <string_view> 17 #include <vector> 18 using namespace std; 19 20 #define N 71 21 22 bool b[N][N]; 23 24 class Qelem { 25 public: 26 int d, x, y; 27 Qelem(int dis, int xx, int yy) : d{dis}, x{xx}, y{yy} {} 28 bool operator<(const Qelem& other) const { return d > other.d; } 29 }; 30 31 32 int coord(int x, int y) { 33 return N*x+y; 34 } 35 36 bool inrange(int x, int y) { 37 return x >= 0 && x < N && y >= 0 && y < N; 38 } 39 40 int shortest_path() { 41 vector<bool> vis(N*N); 42 43 priority_queue<Qelem> q; 44 q.push(Qelem(0, 0, 0)); 45 46 while (!q.empty()) { 47 auto v = q.top(); 48 q.pop(); 49 if (!inrange(v.x, v.y) || b[v.x][v.y] || vis[coord(v.x, v.y)]) 50 continue; 51 if (v.x == N-1 && v.y == N-1) return v.d; 52 vis[coord(v.x, v.y)] = true; 53 q.push(Qelem(v.d+1, v.x+1, v.y)); 54 q.push(Qelem(v.d+1, v.x-1, v.y)); 55 q.push(Qelem(v.d+1, v.x, v.y+1)); 56 q.push(Qelem(v.d+1, v.x, v.y-1)); 57 } 58 return -1; 59 } 60 61 int main() { 62 int x, y; 63 while (cin >> x >> y) { 64 b[x][y] = true; 65 if (shortest_path() == -1) { 66 cout << x << "," << y << endl; 67 exit(0); 68 } 69 } 70 71 cout << "Not found" << endl; 72 73 return 0; 74 }