CC-11 : Find island perimeter.

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. The perimeter of the island is sum of all outward facing sides of cells with 1s. Internal cell sides are not counted as part of perimeter. The input adjacency matrix will have only 1 island. Find the perimeter of island within the input adjacency matrix.

Test cases and expected outputs:

Input Parameters	Expected outputs
Matrix : 1,1,0,0, 1,1,0,0, 1,0,0,0, 1,0,0,0,	Perimeter of island: 12

Pseudocode:

findIslandsPerimeter(int[][] matrix) method:

Initialize a variable named perimeter to store the perimeter of island found.

Set variable rows to matrix.length.

Set variable columns to matrix[0].length.

Initialize a 2 dimensional array called visited with same dimesnions as input matrix.

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:

Increment the variable perimeter by return value of call to findIslandPerimeterDfs (matrix,iIdx,jIdx, perimeter, visited).

Return perimeter.

findIslandPerimeterDfs (int[][] matrix, int i, int j, int perimeter, int[][] visited) method:

if i and j are within index limits of matric and matrix[i][j]=0:

return 1.

If visited[i][j]=1, return 0.

Set visited[i][j]=0; as currentnode has been processed.

Set perimeter int variable to value return by recursive call to findIslandPerimeterDfs (matrix,i+1,j, perimeter, visited).

Increment the variable perimeter by return value of call to findIslandPerimeterDfs (matrix,i-1,j, perimeter, visited).

Increment the variable perimeter by return value of call to findIslandPerimeterDfs (matrix,i,j+1, perimeter, visited).

Increment the variable perimeter by return value of call to findIslandPerimeterDfs (matrix,i,j-1, perimeter, visited).

Return perimeter.

Code:

public int findIslandPerimeterDfs(int[][] matrix, int i, int j, int perimeter,int[][] visited){
	if  ((i < 0 ) || (i >= matrix.length)
			|| (j < 0 ) ||(j >= matrix[0].length) 
			|| (matrix[i][j] == 0)){
		return 1;
	}
	if (visited[i][j]==1) {
		return 0;
	}
	visited[i][j]=1;
	perimeter=findIslandPerimeterDfs(matrix, i+1, j,perimeter, visited);
	perimeter+=findIslandPerimeterDfs(matrix, i-1, j,perimeter, visited);
	perimeter+=findIslandPerimeterDfs(matrix, i, j+1,perimeter, visited);
	perimeter+=findIslandPerimeterDfs(matrix, i, j-1,perimeter, visited);
	return perimeter;
}


public int findIslandsPerimeter(int[][] matrix) {
	int perimeter=0;
	int rows=matrix.length;
	int cols=matrix[0].length;
	int[][] visited=new int[rows][cols];
	for(int iIdx=0; iIdx < rows; iIdx++){
        for(int jIdx=0; jIdx < cols;jIdx++){
           if (!(matrix[iIdx][jIdx]==0)){
        	   perimeter+=findIslandPerimeterDfs(matrix, iIdx, jIdx, perimeter, visited);        	   
        	}
        }
    }
    return perimeter;
}

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 GraphFindIslandPerimeter {

public int findIslandPerimeterDfs(int[][] matrix, int i, int j, int perimeter,int[][] visited){
	if  ((i < 0 ) || (i >= matrix.length)
			|| (j < 0 ) ||(j >= matrix[0].length) 
			|| (matrix[i][j] == 0)){
		return 1;
	}
	if (visited[i][j]==1) {
		return 0;
	}
	visited[i][j]=1;
	perimeter=findIslandPerimeterDfs(matrix, i+1, j,perimeter, visited);
	perimeter+=findIslandPerimeterDfs(matrix, i-1, j,perimeter, visited);
	perimeter+=findIslandPerimeterDfs(matrix, i, j+1,perimeter, visited);
	perimeter+=findIslandPerimeterDfs(matrix, i, j-1,perimeter, visited);
	return perimeter;
}


public int findIslandsPerimeter(int[][] matrix) {
	int perimeter=0;
	int rows=matrix.length;
	int cols=matrix[0].length;
	int[][] visited=new int[rows][cols];
	for(int iIdx=0; iIdx < rows; iIdx++){
        for(int jIdx=0; jIdx < cols;jIdx++){
           if (!(matrix[iIdx][jIdx]==0)){
        	   perimeter+=findIslandPerimeterDfs(matrix, iIdx, jIdx, perimeter, visited);        	   
        	}
        }
    }
    return perimeter;
}

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 {
	GraphFindIslandPerimeter gph=new GraphFindIslandPerimeter();
	int[][] matrix = {	{1,1,0,0},
						{1,1,0,0},	
						{1,0,0,0},
						{1,0,0,0}};
	print2dArray(matrix, "Matrix" );
	retVal=gph.findIslandsPerimeter(matrix);
	System.out.println("Perimeter of island: "+ retVal);
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}