0778.cpp (847B)
1 class Solution { 2 public: 3 int swimInWater(vector<vector<int>> &grid) const { 4 priority_queue<tuple<int, int, int>> pq; 5 const int n = size(grid); 6 7 static const int offset[] = {-1, 0, 1, 0, -1}; 8 const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }; 9 10 pq.emplace(-grid[0][0], 0, 0); 11 while (!pq.empty()) { 12 const auto [t, x, y] = pq.top(); 13 pq.pop(); 14 if (x == n - 1 && y == n - 1) return -t; 15 16 for (int k = 0; k < 4; k++) { 17 const auto a = x + offset[k + 1]; 18 const auto b = y + offset[k]; 19 20 if (!valid(a, b) || grid[a][b] < 0) continue; 21 pq.emplace(min(t, -grid[a][b]), a, b); 22 grid[a][b] = -1; 23 } 24 } 25 26 return -1; 27 } 28 };