Untitled

mail@pastecode.io avatar
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;
    }
}