# 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