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; } };
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter