CC-12 : Count islands within adjacency matrix.

Description:

Given an adjacency matrix filled with Os and 1s. An island is a collection of cells sharing cell boundary in North-South-East-West with other cells with value 1, or sharing boundary with North-South-East-West boundary of matrix. Diagonal touching is not considered as boundary connection. Find the count of islands within the input adjacency matrix.

Test cases and expected outputs:

Input Parameters	Expected outputs
Matrix : 1,0,0,1, 0,0,0,0, 0,0,1,1, 0,0,1,1,	Count of islands: 3
Matrix : 1,0,0,1, 0,0,0,0, 0,0,1,1, 1,0,1,1,	Count of islands: 4

Pseudocode:

countIslands (int[][] matrix) method:

Initialize a variable named islands to store the count of islands found.

Iterate through vertices of matrix using a for loop with iIdx as loop variable with values from 0 to count of matrix.length:

Iterate through vertices of matrix using a for loop with jIdx as loop variable with values from 0 to count of matrix[0].length:

If matrix[iIdx][jIdx] ==0, then increments islands variable by 1.

Call countIslandsDfs(matrix, iIdx, jIdx) recursively.

Return islands.

countIslandsDfs (int[][] matrix, int i, int j) method:

While i and j are within index limits of matric and matrix[i][j]==1:

Set matrix[i][j]=0.

Recursively call findIslandsMaxAreaDfs(matrix,i+1,j).

Recursively call findIslandsMaxAreaDfs(matrix,i-1,j).

Recursively call findIslandsMaxAreaDfs(matrix,i,j+1).

Recursively call findIslandsMaxAreaDfs(matrix,i,j-1).

Code:

public void countIslandsDfs(int[][] matrix, int i, int j){
	while  ((i >= 0 ) && (i < matrix.length)
			&& (j >= 0 ) &&(j < matrix[0].length) 
			&& (matrix[i][j] == 1)){
		matrix[i][j]=0;
		countIslandsDfs(matrix, i+1, j);
		countIslandsDfs(matrix, i-1, j);
		countIslandsDfs(matrix, i, j+1);
		countIslandsDfs(matrix, i, j-1);
	}
}


public int countIslands(int[][] matrix) {
	int islands=0;
	for(int iIdx=0; iIdx < matrix.length; iIdx++){
        for(int jIdx=0; jIdx < matrix[0].length;jIdx++){
           if (!(matrix[iIdx][jIdx]==0)){
        	   
        	   islands=islands+1;
        	   countIslandsDfs(matrix, iIdx, jIdx);
            }
        }
    } 
	return islands;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class GraphFindIslands {

public void countIslandsDfs(int[][] matrix, int i, int j){
	while  ((i >= 0 ) && (i < matrix.length)
			&& (j >= 0 ) &&(j < matrix[0].length) 
			&& (matrix[i][j] == 1)){
		matrix[i][j]=0;
		countIslandsDfs(matrix, i+1, j);
		countIslandsDfs(matrix, i-1, j);
		countIslandsDfs(matrix, i, j+1);
		countIslandsDfs(matrix, i, j-1);
	}
}


public int countIslands(int[][] matrix) {
	int islands=0;
	for(int iIdx=0; iIdx < matrix.length; iIdx++){
        for(int jIdx=0; jIdx < matrix[0].length;jIdx++){
           if (!(matrix[iIdx][jIdx]==0)){
        	   
        	   islands=islands+1;
        	   countIslandsDfs(matrix, iIdx, jIdx);
            }
        }
    } 
	return islands;
}

public static void print2dArray(int[][] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
    if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
    // Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}
	

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	GraphFindIslands gph=new GraphFindIslands();
	int[][] matrix = {	{1,0,0,1},
						{0,0,0,0},	
						{0,0,1,1},
						{0,0,1,1}};
	print2dArray(matrix, "Image Matrix" );
	retVal=gph.countIslands(matrix);
	System.out.println("Count of islands: "+ retVal);
	
	gph=new GraphFindIslands();
	int[][] matrix1 = {	{1,0,0,1},
						{0,0,0,0},	
						{0,0,1,1},
						{1,0,1,1}};
	print2dArray(matrix1, "Image Matrix" );
	retVal=gph.countIslands(matrix1);
	System.out.println("Count of islands: "+ retVal);
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}