day18a.cpp (1172B)
1 #include <algorithm> 2 #include <cstdint> 3 #include <iostream> 4 #include <map> 5 #include <queue> 6 #include <ranges> 7 #include <set> 8 #include <sstream> 9 #include <string> 10 #include <string_view> 11 #include <vector> 12 using namespace std; 13 14 #define N 71 15 #define S 1024 16 17 bool b[N][N]; 18 19 class Qelem { 20 public: 21 int d, x, y; 22 Qelem(int dis, int xx, int yy) : d{dis}, x{xx}, y{yy} {} 23 bool operator<(const Qelem& other) const { return d > other.d; } 24 }; 25 26 27 int coord(int x, int y) { 28 return N*x+y; 29 } 30 31 bool inrange(int x, int y) { 32 return x >= 0 && x < N && y >= 0 && y < N; 33 } 34 35 int shortest_path(bool b[N][N]) { 36 vector<bool> vis(N*N); 37 38 priority_queue<Qelem> q; 39 q.push(Qelem(0, 0, 0)); 40 41 while (!q.empty()) { 42 auto v = q.top(); 43 q.pop(); 44 if (!inrange(v.x, v.y) || b[v.x][v.y] || vis[coord(v.x, v.y)]) 45 continue; 46 if (v.x == N-1 && v.y == N-1) return v.d; 47 vis[coord(v.x, v.y)] = true; 48 q.push(Qelem(v.d+1, v.x+1, v.y)); 49 q.push(Qelem(v.d+1, v.x-1, v.y)); 50 q.push(Qelem(v.d+1, v.x, v.y+1)); 51 q.push(Qelem(v.d+1, v.x, v.y-1)); 52 } 53 return -1; 54 } 55 56 int main() { 57 int x, y; 58 for (int i = 0; i < S && (cin >> x >> y); i++) 59 b[x][y] = true; 60 61 cout << shortest_path(b) << endl; 62 return 0; 63 }