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 
                    //the answer
                    matrix[i][j] = 0;
                    dfs(i, j ,N, M, matrix);
                    ans++;
                }
            }
        }
        return ans;
    }
};