# Untitled

unknown
plain_text
2 years ago
2.0 kB
1
Indexable
Never
```class Solution {
// the idea is to convert all the 1s to 0s in the grid whose parent is a boundary 1.
// standard bfs implementation
class Position{
int x;
int y;
Position(int x, int y){
this.x = x;
this.y = y;
}
}

private void bfs(int [][] grid, int M, int N){
int m = grid.length;
int n = grid[0].length;
Deque<Position> q = new ArrayDeque<>();
q.offer(new Position(M, N));
while(!q.isEmpty()){
Position p = q.poll();
int x = p.x;
int y = p.y;
grid[x][y] = 0;
if(x - 1 >= 0 && grid[x - 1][y] == 1){
q.offer(new Position(x - 1, y));
grid[x - 1][y] = 0;
}
if(y - 1 >= 0 && grid[x][y - 1] == 1){
q.offer(new Position(x, y - 1));
grid[x][y - 1] = 0;
}
if(y + 1 < n && grid[x][y + 1] == 1){
q.offer(new Position(x, y + 1));
grid[x][y + 1] = 0;
}
if(x + 1 < m && grid[x + 1][y] == 1){
q.offer(new Position(x + 1, y));
grid[x + 1][y] = 0;
}
}
}

public int numEnclaves(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if(n == 0) return 0;
for(int i = 0; i < m; i++){
if(grid[i][0] == 1)
bfs(grid, i, 0);
if(grid[i][n - 1] == 1)
bfs(grid, i, n - 1);
}
for(int j = 1; j < n - 1; j++){
if(grid[0][j] == 1)
bfs(grid, 0, j);
if(grid[m - 1][j] == 1)
bfs(grid, m - 1, j);
}
int count = 0;
for(int i [] : grid){
for(int j : i){
// System.out.print(j + " ");
if(j == 1)
count++;
}
// System.out.println();
}
return count;
}
}```