leetcode

0 class Solution {

1 public:

2 int swimInWater(vector<vector<int>> &grid) const {

3 priority_queue<tuple<int, int, int>> pq;

4 const int n = size(grid);

5

6 static const int offset[] = {-1, 0, 1, 0, -1};

7 const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; };

8

9 pq.emplace(-grid[0][0], 0, 0);

10 while (!pq.empty()) {

11 const auto [t, x, y] = pq.top();

12 pq.pop();

13 if (x == n - 1 && y == n - 1) return -t;

14

15 for (int k = 0; k < 4; k++) {

16 const auto a = x + offset[k + 1];

17 const auto b = y + offset[k];

18

19 if (!valid(a, b) || grid[a][b] < 0) continue;

20 pq.emplace(min(t, -grid[a][b]), a, b);

21 grid[a][b] = -1;

22 }

23 }

24

25 return -1;

26 }

27 };