Share my DFS code 24ms C++


  • 0
    H

    I explicitly maintain a box, maintain 4 boundaries: left, right, up, down. Each time we do DFS, we only do it in one direction. So, after 4 directions, we get new 4 boundaries. Repeat this until we can not explore.

    This is different from some other DFS, because we only explore 1 direction each time, this can avoid a lot of redundant work. Only for some special input the performance can be bad. It can even be better than binary search.

    class Solution {
    

    public:
    void DFS(int direction, vector<vector<char>>& image, int startx, int starty, int &nextx, int &nexty, int m, int n){
    image[startx][starty]='a';
    bool explore = false;

        int newx=startx+dx[direction-1];
        int newy=starty+dy[direction-1];
        if(newx>=0 && newx<m && newy>=0 && newy<n && image[newx][newy]=='1'){
            explore == true;
            DFS(direction, image, newx, newy, nextx, nexty, m, n);
        }
    
        image[startx][starty]='1';
        if (explore == false){
            nextx = startx;
            nexty = starty; //in the last step we assign the values. 
        }
    }
    int minArea(vector<vector<char>>& image, int x, int y) {
        //since we have x, y, we 1st find 2 points that for sure contains x,y
        int m=image.size();
        int n=image[0].size();
        int up=x;
        int down=x;
        int left=y;
        int right=y;
    
        int newup=-1;
        int newdown=-1;
        int newleft=-1;
        int newright=-1;
        
        do {
            newup=newdown=newleft=newright=-1;
        
            for(int i=left;i<=right;i++){
                if(image[up][i] =='1' && (up>0 && image[up-1][i]=='1')){
                    newup = up-1; 
                    DFS(1, image, up-1, i, newup, i, m, n);
                    break; //break if found one
                }
            }
        
            for(int i=up;i<=down;i++){
                if(image[i][left] =='1' && (left>0 && image[i][left-1]=='1')){
                    newleft = left-1;
                    DFS(2, image, i, left-1, i, newleft, m, n);
                    break;
                }
            }
    
            for(int i=right;i>=left;i--){
                if(image[down][i] =='1' && (down<m-1 && image[down+1][i]=='1')){
                    newdown = down+1; 
                    DFS(3, image, down+1, i, newdown, i, m, n);
                    break;
                }
            }
        
            for(int i=down;i>=up;i--){
                if(image[i][right] =='1' && (right<n-1 && image[i][right+1]=='1')){
                    newright = right+1;
                    DFS(4, image, i, right+1, i, newright, m, n);
                    break;
                }
            }
    
            if(newup!=-1){
                up=newup;
            }
            if(newdown!=-1){
                down=newdown;
            }
            if(newleft!=-1){
                left=newleft;
            }
            if(newright!=-1){
                right=newright;
            }
        }while ( newup!=-1 || newdown!=-1 || newleft!=-1 || newright!=-1);
        
        return (right-left+1)*(down-up+1);
    }
    

    private:
    int dx[4]={-1, 0, +1, 0};
    int dy[4]={0, -1, 0, +1};
    };


Log in to reply
 

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