In this program, we are going to share a Java program to count islands in boolean 2D matrix. If you are a Java beginner and want to start learning the Java programming, then keep your close attention in this tutorial as I am going to share how to write a Java program to count islands in boolean 2D matrix.
Copy the below Java program and execute it with the help of Javac compiler. At the end of this program, We have shared the output of this program.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
import java.util.*; import java.lang.*; import java.io.*; class Islands { static final int ROW = 5, COL = 5; boolean isSafe(int M[][], int row, int col, boolean visited[][]) { // row number is in range, column number is in range // and value is 1 and not yet visited return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col]==1 && !visited[row][col]); } // A utility function to do DFS for a 2D boolean matrix. // It only considers the 8 neighbors as adjacent vertices void DFS(int M[][], int row, int col, boolean visited[][]) { // These arrays are used to get row and column numbers // of 8 neighbors of a given cell int rowNbr[] = new int[] {-1, -1, -1, 0, 0, 1, 1, 1}; int colNbr[] = new int[] {-1, 0, 1, -1, 1, -1, 0, 1}; // Mark this cell as visited visited[row][col] = true; // Recur for all connected neighbours for (int k = 0; k < 8; ++k) if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited) ) DFS(M, row + rowNbr[k], col + colNbr[k], visited); } int countIslands(int M[][]) { boolean visited[][] = new boolean[ROW][COL]; int count = 0; for (int i = 0; i < ROW; ++i) for (int j = 0; j < COL; ++j) if (M[i][j]==1 && !visited[i][j]) // If a cell with { // value 1 is not // visited yet, then new island found, Visit all // cells in this island and increment island count DFS(M, i, j, visited); ++count; } return count; } // Driver method public static void main (String[] args) throws java.lang.Exception { int M[][]= new int[][] {{1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 1} }; Islands I = new Islands(); System.out.println("Number of islands is: "+ I.countIslands(M)); } } |
Number of islands is: 5
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
