CC-14 : Implement flood fill for image matrix.

Description:

Given an adjacency matrix, implement Floodfill algorithm. Floodfill will start from particular cell containing 1 (oldColor value), and then follow Floodfill path. The Floodfill path can only travel in directions left, right, up down of cells sharing a boundary, but cannot travel diagonal wise. All cells in FLoodfIll path should be set to 3 (newColor value).

Test cases and expected outputs:

Input Parameters	Expected outputs
Image Matrix : 1,1,1,1, 2,1,2,2, 2,2,1,2, 2,2,2,1,	Image Matrix after floodfill : 3,3,3,3, 2,3,2,2, 2,2,1,2, 2,2,2,1,
Image Matrix : 1,1,1,1, 2,1,1,2, 2,2,1,2, 2,2,2,1,	Image Matrix after floodfill : 3,3,3,3, 2,3,3,2, 2,2,3,2, 2,2,2,1,

Pseudocode:

floodFillImageMatrix (int[][] matrix, int i, int j, int oldColor, int newColor) method:

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

Set matrix[i][j]=newColor.

Recursively call floodFillImageMatrix (matrix, i+1, j, int oldColor, int newColor).

Code:

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

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

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

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 {
	GraphFloodFill gph=new GraphFloodFill();
	int[][] matrix = {	{1,1,1,1},
						{2,1,2,2},	
						{2,2,1,2},
						{2,2,2,1}};
	print2dArray(matrix, "Image Matrix" );
	retVal=gph.floodFillImageMatrix(matrix, 0,0,1,3);
	print2dArray(retVal, "Image Matrix after floodfill" );
	
	gph=new GraphFloodFill();
	int[][] matrix1 = {	{1,1,1,1},
						{2,1,1,2},	
						{2,2,1,2},
						{2,2,2,1}};
	print2dArray(matrix1, "Image Matrix" );
	retVal=gph.floodFillImageMatrix(matrix1, 0,0,1,3);
	print2dArray(retVal, "Image Matrix after floodfill" );
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}