Very simple DFS in c++


  • 0
    G
    class Solution {
    public:
        
        long long minRow,maxRow,minCol,maxCol;
        
        Solution():
            minRow(INT_MAX),maxRow(INT_MIN),minCol(INT_MAX),maxCol(INT_MIN){
        }
        
        void visit(int x, int y, vector<vector<char> > &image){
        
            static vector<pair<int,int> > dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            
            minRow = min(minRow,(long long)x);
            maxRow = max(maxRow,(long long)x);
            minCol = min(minCol,(long long)y);
            maxCol = max(maxCol,(long long)y);
             
            image[x][y] = '0';
            
            for(auto &d : dirs){
                int nx = x + d.first;
                int ny = y + d.second;
                
                if(nx >= 0 && ny >= 0 && nx < image.size() && ny < image[x].size() && image[nx][ny] == '1'){
                    visit(nx,ny,image);
                }
            }
        }
        
        int minArea(vector<vector<char>>& image, int x, int y) {
            visit(x,y,image);
            return ((maxRow + 1) - minRow)*((maxCol + 1) - minCol);
        }
    };
    

Log in to reply
 

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