C++ DFS (expanding from edges of Pacific and Atlantic)

• Using vector<vector<bool>>

class Solution {
private:
int m, n, dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};      // up, right, down, left
vector<pair<int, int>> grids;

void expand (vector<vector<int>>& matrix, int r, int c, int bottom, vector<vector<bool>>& a, vector<vector<bool>>& b) {
if (r < 0 || r == m || c < 0 || c == n || matrix[r][c] < bottom || a[r][c]) { return; }
// record current grid reachable by Atlantic and if reachable by both
if ((a[r][c] = true) && b[r][c]) { grids.push_back(make_pair(r, c)); }
for (auto dir: dirs) {                                      // expand
expand(matrix, r + dir[0], c + dir[1], matrix[r][c], a, b);
}
}

public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if ((m = matrix.size()) == 0 || (n = matrix[0].size()) == 0) { return grids; }
vector<vector<bool>> pacific(m, vector<bool>(n, false)), atlantic(m, vector<bool>(n, false));

for (int r = 0; r < m; r++) {
expand(matrix, r, 0, 0, pacific, atlantic);             // expand Pacific
expand(matrix, r, n - 1, 0, atlantic, pacific);         // expand Atlantic
}
for (int c = 0; c < n; c++) {
expand(matrix, 0, c, 0, pacific, atlantic);             // expand Pacific
expand(matrix, m - 1, c, 0, atlantic, pacific);         // expand Atlantic
}

return grids;
}
};

Using unordered_set<int>

class Solution {
private:
int m, n, dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};      // up, right, down, left
vector<pair<int, int>> grids;

void expand (vector<vector<int>>& matrix, int r, int c, int bottom, unordered_set<int>& a, unordered_set<int>& b) {
int k = r * n + c;                                          // hash table key
if (r < 0 || r == m || c < 0 || c == n || matrix[r][c] < bottom || a.count(k)) { return; }
a.insert(k);                                                // record current grid reachable by Atlantic
if (b.count(k)) { grids.push_back(make_pair(r, c)); }       // record grid if reachable by both
for (auto dir: dirs) {                                      // expand
expand(matrix, r + dir[0], c + dir[1], matrix[r][c], a, b);
}
}

public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if ((m = matrix.size()) == 0 || (n = matrix[0].size()) == 0) { return grids; }
unordered_set<int> pacific, atlantic;

for (int r = 0; r < m; r++) {
expand(matrix, r, 0, 0, pacific, atlantic);             // expand Pacific
expand(matrix, r, n - 1, 0, atlantic, pacific);         // expand Atlantic
}
for (int c = 0; c < n; c++) {
expand(matrix, 0, c, 0, pacific, atlantic);             // expand Pacific
expand(matrix, m - 1, c, 0, atlantic, pacific);         // expand Atlantic
}

return grids;
}
};

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