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