Advertisement
Guest User

Grokking #201

a guest
Dec 12th, 2021
44
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.  
  3. int[][] grid;
  4. int rows;
  5. int cols;
  6.  
  7. int[][] dirs = new int[][] { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
  8.  
  9. public int closedIsland(int[][] grid) {
  10. this.grid = grid;
  11. this.rows = grid.length;
  12. this.cols = grid[0].length;
  13.  
  14. for (int r = 0; r < rows; r++) {
  15. for (int c = 0; c < cols; c++) {
  16.  
  17. // if cell is zero and is at edge, mark it invalid
  18. if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) {
  19. fill(r, c);
  20. }
  21.  
  22. }
  23. }
  24.  
  25. // count number of islands
  26. int count = 0;
  27. for (int r = 0; r < rows; r++) {
  28. for (int c = 0; c < cols; c++) {
  29.  
  30. if (grid[r][c] == 0) {
  31. count++;
  32.  
  33. fill(r, c);
  34. }
  35.  
  36. }
  37. }
  38.  
  39. return count;
  40. }
  41.  
  42. void fill(int r, int c) {
  43. if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 0) {
  44. return;
  45. }
  46.  
  47. grid[r][c] = 1;
  48.  
  49. for (int[] dir : dirs) {
  50. int rr = r + dir[0];
  51. int cc = c + dir[1];
  52.  
  53. fill(rr, cc);
  54. }
  55. }
  56. }
  57.  
Advertisement
RAW Paste Data Copied
Advertisement