CC-15 : Replaces Os with Xs.

Description:

Given an adjacency matrix, filled with Os and Xs. For each O, Replace O by X, if there is no path of Os from current O to boundary of matrix. Os path can be in left, right, top, bottom direction only and not diagonal wise.

Test cases and expected outputs:

Input Parameters	Expected outputs
Original Matrix : X,O,X,O, O,X,O,X, X,X,O,X, X,X,X,X,	Image Matrix after Replace O by X : X,O,X,O, O,X,X,X, X,X,X,X, X,X,X,X,
Original Matrix : X,O,X,O,X, O,X,O,O,X, X,X,X,X,X, O,X,X,O,X, X,O,X,X,X,	Image Matrix after Replace O by X : X,X,X,X,X, X,X,X,X,X, X,X,X,X,X, X,X,X,X,X, X,X,X,X,X,

Pseudocode:

replaceOByX (int[][] matrix) method:

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:

Set the Os to ‘ ‘;to indicate these cells need to be processed.

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 first column or last column cells are ‘ ‘, call dfsReplaceOByX(matrix, iIdx, jIdx, ‘ ‘, ‘O’).

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 top row or bottom row cells are ‘ ‘, call dfsReplaceOByX(matrix, iIdx, jIdx, ‘ ‘, ‘O’).

Return matrix.

dfsReplaceOByX (int[][] matrix, int iIdx, int jIdx, int oldColor, int newColor) method:

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

Set matrix[iIdx][ jIdx]=newColor.

Recursively call floodFillImageMatrix (matrix, iIdx +1, jIdx, int oldColor, int newColor).

Code:

public void dfsReplaceOByX(char[][] matrix, int iIdx, int jIdx, char oldChar, char newChar) {
	while  ((iIdx >= 0 ) && (iIdx < matrix.length)
			&& (jIdx >= 0 ) &&(jIdx < matrix[0].length) 
			&& (matrix[iIdx][jIdx] == oldChar)){
		matrix[iIdx][jIdx]=newChar;
		dfsReplaceOByX(matrix, iIdx+1, jIdx, oldChar, newChar);
		dfsReplaceOByX(matrix, iIdx-1, jIdx, oldChar, newChar);
		dfsReplaceOByX(matrix, iIdx, jIdx+1, oldChar, newChar);
		dfsReplaceOByX(matrix, iIdx, jIdx-1, oldChar, newChar);
	}
}

public char[][] replaceOByX(char[][] matrix) throws Exception{
	for (int iIdx=0; iIdx < matrix.length; iIdx++) {
		for (int jIdx=0; jIdx < matrix[0].length; jIdx++) {
			if (matrix[iIdx][jIdx] =='O'){
					matrix[iIdx][jIdx]=' ';
			}
		}		
	}
	for (int iIdx=0; iIdx < matrix.length; iIdx++) {
		if (matrix[iIdx][0] ==' '){
			dfsReplaceOByX(matrix, iIdx, 0,' ', 'O');
		}
		if (matrix[iIdx][matrix[0].length-1] ==' '){
			dfsReplaceOByX(matrix, iIdx, matrix[0].length-1,' ', 'O');
		}
	}
	for (int jIdx=0; jIdx < matrix[0].length; jIdx++) {
		if (matrix[0][jIdx] ==' '){
			dfsReplaceOByX(matrix, 0, jIdx,' ', 'O');
		}
		if (matrix[matrix.length-1][jIdx] ==' '){
			dfsReplaceOByX(matrix, matrix.length-1, jIdx,' ', 'O');
		}
	}
	for (int iIdx=0; iIdx < matrix.length; iIdx++) {
		for (int jIdx=0; jIdx < matrix[0].length; jIdx++) {
			if (matrix[iIdx][jIdx] ==' '){
					matrix[iIdx][jIdx]='X';
			}
		}		
	}
	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 GraphReplaceOByX {


public void dfsReplaceOByX(char[][] matrix, int iIdx, int jIdx, char oldChar, char newChar) {
	while  ((iIdx >= 0 ) && (iIdx < matrix.length)
			&& (jIdx >= 0 ) &&(jIdx < matrix[0].length) 
			&& (matrix[iIdx][jIdx] == oldChar)){
		matrix[iIdx][jIdx]=newChar;
		dfsReplaceOByX(matrix, iIdx+1, jIdx, oldChar, newChar);
		dfsReplaceOByX(matrix, iIdx-1, jIdx, oldChar, newChar);
		dfsReplaceOByX(matrix, iIdx, jIdx+1, oldChar, newChar);
		dfsReplaceOByX(matrix, iIdx, jIdx-1, oldChar, newChar);
	}
}

public char[][] replaceOByX(char[][] matrix) throws Exception{
	for (int iIdx=0; iIdx < matrix.length; iIdx++) {
		for (int jIdx=0; jIdx < matrix[0].length; jIdx++) {
			if (matrix[iIdx][jIdx] =='O'){
					matrix[iIdx][jIdx]=' ';
			}
		}		
	}
	for (int iIdx=0; iIdx < matrix.length; iIdx++) {
		if (matrix[iIdx][0] ==' '){
			dfsReplaceOByX(matrix, iIdx, 0,' ', 'O');
		}
		if (matrix[iIdx][matrix[0].length-1] ==' '){
			dfsReplaceOByX(matrix, iIdx, matrix[0].length-1,' ', 'O');
		}
	}
	for (int jIdx=0; jIdx < matrix[0].length; jIdx++) {
		if (matrix[0][jIdx] ==' '){
			dfsReplaceOByX(matrix, 0, jIdx,' ', 'O');
		}
		if (matrix[matrix.length-1][jIdx] ==' '){
			dfsReplaceOByX(matrix, matrix.length-1, jIdx,' ', 'O');
		}
	}
	for (int iIdx=0; iIdx < matrix.length; iIdx++) {
		for (int jIdx=0; jIdx < matrix[0].length; jIdx++) {
			if (matrix[iIdx][jIdx] ==' '){
					matrix[iIdx][jIdx]='X';
			}
		}		
	}
	return matrix;	
}

public static void print2dArray(char[][] 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:
	 **********************/
	char[][] retVal;
	try {
	GraphReplaceOByX gph=new GraphReplaceOByX();
	char[][] matrix = {	{'X','O','X','O'},
						{'O','X','O','X'},	
						{'X','X','O','X'},
						{'X','X','X','X'}};
	print2dArray(matrix, "Original Matrix" );
	retVal=gph.replaceOByX(matrix);
	print2dArray(retVal, "Image Matrix after Replace O by X" );
	
	gph=new GraphReplaceOByX();
	char[][] matrix1 = {{'X','O','X','O','X'},
						{'O','X','O','O','X'},	
						{'X','X','X','X','X'},
						{'O','X','X','O','X'},
						{'X','O','X','X','X'}};
	print2dArray(matrix1, "Original Matrix" );
	retVal=gph.replaceOByX(matrix1);
	print2dArray(retVal, "Image Matrix after Replace O by X" );
	
	gph=new GraphReplaceOByX();
	char[][] matrix2 = {{'X','X','X','X','X'},
						{'X','X','O','X','X'},	
						{'X','O','O','O','X'},
						{'X','X','O','X','X'},
						{'X','X','X','X','X'}};
	print2dArray(matrix2, "Original Matrix" );
	retVal=gph.replaceOByX(matrix2);
	print2dArray(retVal, "Image Matrix after Replace O by X" );
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}



}