```class Solution {
public:
int closedIslands(vector<vector<int>>& matrix, int N, int M) {
// Code here
queue<pair<int,int>> q;
for(int i = 0; i < N ; i++){
for(int j = 0; j < M; j++){
if(matrix[i][j] == 1 && (i == 0 || j == 0 || i == N-1 || j == M-1))
q.push({i,j}),matrix[i][j] = 0;
}
}
auto bfs = [&q,&matrix,N,M]()->void{
auto isSafe = [N, M](int x, int y)->bool{
return x>=0 && y>=0 && x<N && y<M;
};
while(!q.empty()){
auto curr = q.front();
q.pop();
vector<pair<int,int>> dir{
{1,0},
{0,-1},
{-1,0},
{0,1}
};
for(auto p : dir){
int x = p.first+ curr.first , y = p.second + curr.second;
if(isSafe(x, y) && matrix[x][y] == 1 )
q.push({x,y}), matrix[x][y] = 0;
}
}
};
bfs();
int ans = 0;
for(int i = 0; i < N; i++){
for(int j = 0 ; j<M; j++){
if(matrix[i][j]){
matrix[i][j] = 0;
q.push({i,j});
bfs(),ans++;
}
}
}
return ans;
}
};```
```class Solution {
public:
vector<int> dx{0, 1, -1, 0},dy{1, 0, 0, -1};
bool isVisitable(int x, int y, int N, int M){
return x>=0 && y>=0 && x<N && y<M;
}
void dfs(int i, int j, int N, int M, vector<vector<int>>& matrix){
for(int k =0 ; k <4; k++){
int x = i + dx[k], y = j + dy[k];
if( isVisitable(x, y, N, M) && matrix[x][y] != 0)
matrix[x][y]=0,dfs(x, y, N, M, matrix);
}
}
int closedIslands(vector<vector<int>>& matrix, int N, int M) {
// Code here
for(int i = 0; i < N; i++){
for(int j = 0; j < M ; j++){
if( (i == 0 || j == 0 || i == N -1 || j == M - 1 )&& matrix[i][j] == 1){
//check if 1 exists on the edges of matrix
//if yes visit all the cells that have 1 and are
//reachable from current cell and mark them visited by making 0
matrix[i][j] = 0;
dfs(i, j, N, M,matrix);
}
}
}

int ans = 0;
for(int i = 0 ; i < N; i++){
for(int j = 0; j < M ; j++){
if(matrix[i][j] == 1){
//whatever cells not visited in previous case
//we visit now and mark visited(0) and increment the
matrix[i][j] = 0;
dfs(i, j ,N, M, matrix);
ans++;
}
}
}
return ans;
}
};```
star

Thu May 18 2023 19:59:59 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/find-number-of-closed-islands/1

#bfs #closedislands #lambda_functions
star

Thu May 18 2023 19:36:49 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/find-number-of-closed-islands/1

#dfs #closedislands