Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.0 kB
2
Indexable
Never
class Solution {
public:
    int islcount(vector<vector<int>>& grid,vector<pair<int,int>>&directions){  //returns no of islands by using bfs on matrix
        int ans=0;
        vector<vector<bool>> vis(grid.size(),vector<bool>(grid[0].size(),false));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){

                if(grid[i][j]==1 && !vis[i][j]){ // do bfs and make all grids in this island visited
                    ans+=1;
                    vis[i][j]=1;
                    queue<pair<int,int>>q;
                    q.push({i,j});

                    while(!q.empty()){
                        pair<int,int> p=q.front();
                        q.pop();
                        int x=p.first, y=p.second;
                        for(auto d:directions){
                            int new_x = x+d.first;
                            int new_y= y+d.second;
                            if( 0<=new_x && new_x<grid.size() && 0<=new_y && new_y <grid[0].size() && !vis[new_x][new_y] && grid[new_x][new_y]==1){
                                q.push({new_x,new_y});
                                vis[new_x][new_y]=1;
                            }
                        }
                    } 
                }
            }
        }
        return ans;
    }

    int minDays(vector<vector<int>>& grid) {
        vector<pair<int,int>> directions={{-1,0},{1,0},{0,-1},{0,1}}; //up,down,left,right
        int c=islcount(grid,directions);
        if(c>1) return 0;
        if(c==0) return 0;
        else{
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[0].size();j++){
                    if(grid[i][j]==1){
                        grid[i][j]=0;
                        if(islcount(grid,directions)>1 || islcount(grid,directions)==0) return 1;

                        grid[i][j]=1;
                    }
                }
            }
            return 2;
        }   
    }
};