1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

typedef std::pair<int, std::pair<int, int>> PIPII;

class Solution {
public:
    int swimInWater(std::vector<std::vector<int>>& grid) {
        int n = grid.size();
        std::vector<std::vector<int>> dist(n, std::vector<int>(n, 0x3fff'ffff));
        std::priority_queue<PIPII, std::vector<PIPII>, std::greater<PIPII>> pq;
        
        dist[0][0] = grid[0][0];
        pq.push({dist[0][0], {0, 0}});
        int dirs[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
        
        while (!pq.empty()) {
            int d = pq.top().first;
            int x = pq.top().second.first;
            int y = pq.top().second.second;
            pq.pop();
            if (x == n - 1 && y == n - 1) {
                return d;
            }
            if (d > dist[x][y]) {
                continue;
            }
            
            for (auto& dir : dirs) {
                int xx = x + dir[0];
                int yy = y + dir[1];
                if (xx >= 0 && xx < n && yy >= 0 && yy < n) {
                    int nd = std::max(d, grid[xx][yy]);
                    if (nd < dist[xx][yy]) {
                        dist[xx][yy] = nd;
                        pq.push({nd, {xx, yy}});
                    }
                }
            }
        }
        
        return -1;
    }
};