# Untitled

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