1
class Solution {
2
 public:
3
  int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
4
  bool valid(int x, int y, int n) {
5
    return ((x >= 0 && x < n) && (y >= 0 && y < n));
6
  }
7
  int swimInWater(vector<vector<int>> &grid) {
8
    int n = grid.size();
9
    int time[n][n];
10
    bool vis[n][n];
11
    for (int i = 0; i < n; ++i) {
12
      for (int j = 0; j < n; ++j) {
13
        time[i][j] = 1e9;
14
        vis[i][j] = false;
15
      }
16
    }
17
    time[0][0] = grid[0][0];
18
    priority_queue<tuple<int, int, int>> q;
19
    q.push({-time[0][0], 0, 0});
20
    while (!q.empty()) {
21
      tuple<int, int, int> node = q.top();
22
      q.pop();
23
      int x = get<1>(node), y = get<2>(node);
24
      if (vis[x][y]) continue;
25
      vis[x][y] = true;
26
      for (int i = 0; i < 4; ++i) {
27
        int xc = x + dir[i][0], yc = y + dir[i][1];
28
        if (!valid(xc, yc, n)) continue;
29
        if (time[x][y] < grid[xc][yc]) {
30
          time[xc][yc] = grid[xc][yc];
31
          q.push({-time[xc][yc], xc, yc});
32
        } else {
33
          if (time[xc][yc] > time[x][y]) {
34
            time[xc][yc] = time[x][y];
35
            q.push({-time[xc][yc], xc, yc});
36
          }
37
        }
38
      }
39
    }
40
    return time[n - 1][n - 1];
41
  }
42
};
43
// Time: O(N*N+N*NLOG(N*N))
44
// Space: O(N*N)