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


  • 0

    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;
        }
    };
    

Log in to reply
 

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