C++ DFS -- from the ocean


  • 0

    just gonna share my solution, but seems I am a little bit too late; there is an another sharing already https://discuss.leetcode.com/topic/62314/very-concise-c-solution-using-dfs-and-bit-mask

    And here is my code:

        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            int w = matrix.size();
            if(!w)return {};
            int h = matrix[0].size();
            
            vector<vector<int>> vv(w,vector<int>(h,0));
            for(int i=0;i<w;++i) {
                explore<1>(matrix,vv,i,0,INT_MIN);
                explore<2>(matrix,vv,i,h-1,INT_MIN);
            }
            for(int i=0;i<h;++i) {
                explore<1>(matrix,vv,0,i,INT_MIN);
                explore<2>(matrix,vv,w-1,i,INT_MIN);
            }
            vector<pair<int,int>> ret;
            for(int i=0;i<w;++i) for(int j=0;j<h;++j) if(vv[i][j] == 3)ret.push_back({i,j});
            return ret;
        }
        template<int MASK>
        void explore(const vector<vector<int>>& matrix, vector<vector<int>>& vv, int x, int y, int h) {
            if(x<0 || y<0 || x>=matrix.size() || y>=matrix[x].size())return;
            if(vv[x][y]&MASK) return;
            if(h > matrix[x][y]) return;
            vv[x][y] |= MASK;
            h = matrix[x][y];
            explore<MASK>(matrix,vv,x-1,y,h);
            explore<MASK>(matrix,vv,x+1,y,h);
            explore<MASK>(matrix,vv,x,y-1,h);
            explore<MASK>(matrix,vv,x,y+1,h);
        }
    

Log in to reply
 

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