1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| class Solution { void bfs(vector<vector<int>>& matrix, int sy, int sx, int n, int m) { int dy[4]{-1,0,1,0},dx[4]{0,1,0,-1}; queue<pair<int,int>> q; matrix[sy][sx] = 0; q.push({sy,sx}); while(!q.empty()) { auto p = q.front(); q.pop(); auto y = p.first, x = p.second; for(int i = 0 ; i < 4 ; i++) { int ny = y + dy[i], nx = x + dx[i]; if(0 <= ny and ny < n and 0 <= nx and nx < m and matrix[ny][nx] == 1) { matrix[ny][nx] = 0; q.push({ny,nx}); } } } } public: int closedIslands(vector<vector<int>>& matrix, int N, int M) { int res = 0; for(int i = 0; i < N; i++) { if(matrix[i][0] == 1) bfs(matrix, i, 0, N, M); if(matrix[i][M - 1] == 1) bfs(matrix, i, M - 1, N, M); } for(int i = 0; i < M; i++) { if(matrix[0][i] == 1) bfs(matrix,0,i,N,M); if(matrix[N-1][i] == 1) bfs(matrix,N-1,i,N,M); } for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { if(matrix[i][j]) { res++; bfs(matrix,i,j,N,M); } } } return res; } };
|