Connected Cells in a Grid

I received a message from HackerRank to give the Connected Cells in a Grid challenge a try. If interested, please take a look at the requirements and see if we agree with the approach I took to solve the challenge.

It seems like this challenge is asking for some type of graph traversal approach. When dealing with graphs the number of vertices may become an issue rather quickly. I took a look at the constraints for the challenge:  0 < n , m < 10. In this case size of the graph is not an issue so the graph representation (graph data structure) could be implemented as an adjacency matrix. I will do a follow up post on this challenge with a solution that would work when the graph has a few more vertices. In general the density of graphs is relatively low. In this case density is also not a concern.

Following is a screen capture of the Eclipse IDE running sample and test data some of which was modified while developing the solution:

4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0
5

2
2
1 1
0 1
3

3
3
0 1 0
0 1 0 
1 1 1
5

4
4
1 1 0 1
1 1 0 0
0 0 1 0
1 0 0 1
6

My solution in Java 8 follows:

import java.util.Scanner;

public class Solution {

	/**
	 * Determine the size of the current region.
	 * Recursive method.
	 */
	static int region(int rows, int cols, boolean matrix[][], int r, int c) {		

		// **** ****
		
		int size 		= 1;
		matrix[r][c] 	= false;		
		
		// **** N ****
		
		if ((r > 0) && matrix[r - 1][c]) {
			size += region(rows, cols, matrix, r - 1, c);
		}
				
		// **** NE ****
		
		if ((r > 0) && (c < cols - 1) && matrix[r - 1][c + 1]) {
			size += region(rows, cols, matrix, r - 1, c + 1);			
		}
		
		// **** E ****
		
		if ((c < cols - 1) && matrix[r][c + 1]) {
			size += region(rows, cols, matrix, r, c + 1);
		}
		
		// **** SE ****
		
		if ((r < rows - 1) && (c < cols - 1) && matrix[r + 1][c + 1]) {
			size += region(rows, cols, matrix, r + 1, c + 1);			
		}
		
		// **** S ****
		
		if ((r < rows - 1) && matrix[r + 1][c]) {
			size += region(rows, cols, matrix, r + 1, c);
		}
		
		// **** SW ****
		
		if ((r < rows - 1) && (c > 0) && matrix[r + 1][c - 1]) {
			size += region(rows, cols, matrix, r + 1, c - 1);			
		}

		// **** W ****
		
		if ((c > 0) && matrix[r][c - 1]) {
			size += region(rows, cols, matrix, r, c - 1);						
		}

		// **** NW ****
	
		if ((r > 0) && (c > 0) && matrix[r - 1][c - 1]) {
			size += region(rows, cols, matrix, r - 1, c - 1);									
		}

		// **** return the size ****
		
		return size;
	}
	
	/**
	 * Determine the maximum size of all regions.
	 */
	static int largestRegion(int rows, int cols, boolean[][] matrix) {
		int size = 0;
	
		// **** loop once per cell in the matrix ****
		
		for (int r = 0; r < rows; r++) {
			for (int c = 0; c < cols; c++) {
				if (matrix[r][c] == true) {
					size = Math.max(size, region(rows, cols, matrix, r, c));
				}
			}
		}
		
		// **** return max size ****
		
		return size;
	}
	
	/**
	 * Test code.
	 */
	public static void main(String[] args) {
		
		// **** open scanner ****
		
		Scanner sc = new Scanner(System.in);
		
		// **** read matrix dimensions ****
		
		int rows = sc.nextInt();
		int cols = sc.nextInt();
		
		// **** ****
		
		boolean[][] matrix = new boolean[rows][cols];
		
		// **** load the matrix ****
		
		for (int r = 0; r < rows; r++) {
			for (int c = 0; c < cols; c++) {
				matrix[r][c] = (sc.nextInt() == 0) ? false : true;
			}
		}

		// **** display the matrix ****
		
//		System.out.println("main <<< matrix:");
//		for (int r = 0; r < rows; r++) {
//			for (int c = 0; c < cols; c++) {
//				System.out.print(matrix[r][c] ? "1 " : "0 ");
//			}
//			System.out.println();
//		}

		// **** close scanner ****
		
		sc.close();
		
		// **** determine and display the size of the largest region ****
		
		System.out.println(largestRegion(rows, cols, matrix));
	}

}

The code passed the seven test cases.

If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. Will reply as soon as possible and will not use your name unless you explicitly allow me to do so.

Enjoy;

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa