rahools

Untitled

Aug 5th, 2021
662
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Islands {
  2.     static final int ROW = 5, COL = 5;
  3.  
  4.     boolean isSafe(int M[][], int row, int col, boolean visited[][])
  5.     {
  6.         return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
  7.     }
  8.  
  9.     // A utility function to do DFS for a 2D boolean matrix.
  10.     // It only considers the 8 neighbors as adjacent vertices
  11.     int DFS(int M[][], int row, int col, boolean visited[][])
  12.     {
  13.         int rowNbr[] = new int[] { -1, 0, 0, 1 };
  14.         int colNbr[] = new int[] { 0, -1, 1, 0 };
  15.  
  16.         // Mark this cell as visited
  17.         visited[row][col] = true;
  18.  
  19.         // Recur for all connected neighbours
  20.         int count = 1;
  21.         for (int k = 0; k < 8; ++k)
  22.             if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
  23.                 count += DFS(M, row + rowNbr[k], col + colNbr[k], visited);
  24.  
  25.         return count
  26.     }
  27.  
  28.     boolean diagCheck(int M[][], int row, int col) {
  29.         int rowNbr[] = new int[] { -1, 1, -1,  1 };
  30.         int colNbr[] = new int[] { 1, -1, -1, 1 };
  31.  
  32.         boolean ans = true;
  33.         for(int k = 0; k < 4; k++) {
  34.             if i >= 0 and i < ROW and j >= 0 and j < COL {
  35.                 ans = ans and M[i + rowNbr[k]][j + colNbr[k]] == 0;
  36.             }
  37.         }
  38.         return ans;
  39.     }
  40.  
  41.     // The main function that returns count of islands in a given
  42.     // boolean 2D matrix
  43.     int countIslands(int M[][])
  44.     {
  45.         // Make a bool array to mark visited cells.
  46.         // Initially all cells are unvisited
  47.         boolean visited[][] = new boolean[ROW][COL];
  48.  
  49.         // Initialize count as 0 and traverse through the all cells
  50.         // of given matrix
  51.         int count = 0, temp;
  52.         for (int i = 0; i < ROW; ++i)
  53.             for (int j = 0; j < COL; ++j)
  54.                 if (M[i][j] == 1 && !visited[i][j]) // If a cell with
  55.                 { // value 1 is not
  56.                     // visited yet, then new island found, Visit all
  57.                     // cells in this island and increment island count
  58.  
  59.                     temp = DFS(M, i, j, visited);
  60.                     if (temp > 1) {
  61.                         ++ count;
  62.                     }
  63.                     else {
  64.                         if diagCheck(M, i, j)
  65.                             count += 1
  66.                     }
  67.                 }
  68.  
  69.         return count;
  70.     }
  71.  
  72.     // Driver method
  73.     public static void main(String[] args) throws java.lang.Exception
  74.     {
  75.         int M[][] = new int[][] { { 1, 1, 0, 0, 0 },
  76.                                   { 0, 1, 0, 0, 1 },
  77.                                   { 1, 0, 0, 1, 1 },
  78.                                   { 0, 0, 0, 0, 0 },
  79.                                   { 1, 0, 1, 0, 1 } };
  80.         Islands I = new Islands();
  81.         System.out.println("Number of islands is: " + I.countIslands(M));
  82.     }
  83. } // Contributed by Aakash Hasija
RAW Paste Data