Not so short but easily understandable BSF priority queue C++ solution


  • 0

    This problem is very similar to 2D Rain Trap Water. The ocean's boundary cells are added to priority queue first and then propagate to the neighboring cells of the top of queue. A struct "Height" is created to store x-y coordinates, height, flow accessible, visited flags. The comparator of priority queue is defined by the "greater" comparison of cell's height since the water can only flow from equal or higher elevation to lower one. I am only making the code readable and didn't optimize on space usage.

    public:
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& a) {
      vector<pair<int, int>> res;
      m = a.size(); if (!m) return res;
      n = a[0].size(); if (!n) return res;
      cells.resize(m);
      // create cells and initialize queues for pacific and atlantic
      for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
          cells[i].emplace_back(i, j, a[i][j]);
          if (i == 0 || j == 0) {
            cells[i][j].flow |= 1; cells[i][j].visited |= 1;
            pacific.push(cells[i][j]);
          }
          if (i == m - 1 || j == n - 1) {
            cells[i][j].flow |= 1 << 1; cells[i][j].visited |= 1 << 1;
            atlantic.push(cells[i][j]);
          }
        }
      // set flow flags for both oceans
      setFlow(0); setFlow(1);
      // get locations accessible to both oceans
      for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
          if (cells[i][j].flow == 3) res.emplace_back(i, j);
      return res;
    }
    
    private:
    // BSF: set flow and visited flags for an ocean
    void setFlow(int isAtlantic) {
      auto q = isAtlantic? atlantic : pacific;
      while (!q.empty()) {
        auto cur = q.top(); q.pop();
        for (auto& d : dirs) {
          int i = cur.x + d[0], j = cur.y + d[1];
          if (i < 0 || i >= m || j < 0 || j >= n || (cells[i][j].visited&(1<< isAtlantic))) continue;
          cells[i][j].visited |= (1 << isAtlantic);
          if (cells[i][j].h >= cur.h) {
            cells[i][j].flow |= 1 << isAtlantic; q.push(cells[i][j]);
          }
        }
      }
    }
    
    struct Height {
      int x, y, h;
      int flow;    // 2-bit binary 00: low bit for Pacific, high bit for Atlantic
      int visited; // 2-bit binary 00: low bit for Pacific, high bit for Atlantic
      Height(int xx, int yy, int hh) :flow(0), visited(0), x(xx), y(yy), h(hh) {}
    };
    
    struct HComp {
      bool operator()(Height a, Height b) { return a.h > b.h; }
    };
    
    int m, n; // grid dimensions
    vector<vector<Height>> cells; 
    priority_queue<Height, vector<Height>, HComp> pacific, atlantic;
    vector<vector<int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.