778. Swim in Rising Water

778. Swim in Rising Water

 

Complexity: O(n^2)

Topic: Flood Fill

Solution:

class Solution {
public:
    using vi = vector<int>;
struct pos
{
  pos(int a, int b, int c) : val(a), x (b), y(c) {}
  bool operator< (const pos &d) const {return val > d.val;}
  int val, x,y;
};

vi nx = {1,-1,0,0};
vi ny = {0, 0, 1, -1};

bool is_valid(int x, int y, int n)
{
  return (x >= 0 && x < n && y >= 0 &&  y < n);
}

int swimInWater (vector<vector<int>>& grid)
{
  int n = grid.size();

  priority_queue<pos>PQ;

  PQ.push(pos(grid[0][0], 0, 0));

  vector<vector<int>> done(n, vi (n, -1));
  done[0][0] = grid[0][0];

  while(done[n-1][n-1] == -1){
    auto p = PQ.top();
    PQ.pop();

    for(int i = 0; i < 4; i++){
      int a = p.x + nx[i];
      int b = p.y + ny[i];

      if(is_valid(a,b,n) && done[a][b] == -1){
        int c = max(grid[a][b], p.val);
        PQ.push(pos(c,a,b));
        done[a][b] = c;
      }
    }
  }
  return done[n-1][n-1];
}
};

Share: