Untitled
unknown
plain_text
3 years ago
2.0 kB
4
Indexable
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; } }
Editor is loading...