Matrix Search – find group of connected-1s/sectors in a matrix

find length of connected cells of 1s(sector) in an matrix of 0s and 1s?
find number of islands in a matrix?
find connected sectors of a matric?
implementation of flood fill algorithm?
All these questions are same, below are the implementation details

Full source code can be downloaded from here

Consider a two-dimensional grid of cells, each of which may be empty or filled. The filled cells that are connected form a sector. Two cells are said to be connected if they are adjacent to each other horizontally, vertically or diagonally. There may be several sectors on the grid. Your job is to find the largest sector (in terms of number of cells) on the grid.

The following figure illustrates a grid with 3 sectors (the largest contains 5 cells).
grid

Problem
Write a program that determines the size of the largest sector for a given grid.

Input
The input begins with a single positive integer on a line by itself indicating the number of the cases
following, each of them as described below. This line is followed by a blank line, and there is also a blank
line between two consecutive inputs. The grid is given as a set of string, each composed of 0s and 1s.
The 1 indicates that the cell is filled and 0 indicates an empty cell. The strings should be converted into
the grid format. The largest grid that should be considered is a 25×25 grid.

Attached is the input file:
input.txt

Output
For each test case, the output must follow the description below. The outputs of two consecutive cases
will be separated by a blank line. The output is the size of the largest sector found on the grid.

Sample Input
2

11000
01100
00101
10001
01011

1011
1010

Sample Output
5
3

This solution is a recursion of depth of 8 levels :

int findMaxDepth(int[][] n, boolean[][] bool, int i, int j) {
	// Check if i, j (indexes) are within the size of array
	// Check if the cell is already traversed or not using bool array
	// Check if the cell value is 1 before counting it as part of a sector
	if(i >= 0 && i < n.length &&  				j >=0 && j < n[0].length
				&& bool[i][j] != true && n[i][j] != 0) {
		currentDepth++;

		// Mark the status of the cell for backtracking purpose
		bool[j] = true;

		// left traversal
		findMaxDepth(n, bool, i-1, j);
		// right traversal
		findMaxDepth(n, bool, i+1, j);

		// top traversal
		findMaxDepth(n, bool, i, j-1);
		// bottom traversal
		findMaxDepth(n, bool, i, j+1);

		// Top-Bottom diagnol
		// diagnol-down traversal
		findMaxDepth(n, bool, i+1, j+1);
		// diagnol-up traversal
		findMaxDepth(n, bool, i-1, j-1);

		// Bottom-Top diagnol
		// diagnol-down traversal
		findMaxDepth(n, bool, i+1, j-1);
		// diagnol-up traversal
		findMaxDepth(n, bool, i-1, j+1);
	}
	return currentDepth;
}

Full source code can be downloaded from here

Attaching the problem statement, input.txt.
counting_cell
 

Advertisements

4 Responses to Matrix Search – find group of connected-1s/sectors in a matrix

  1. Ben Ritchie says:

    Better than my imperative solution (http://java.dzone.com/articles/thursday-code-puzzler-matrix-search#comment-98739) but i think you need to return max of all your recursions and pass currentMaxDepth thru params right?

    • Niranjan says:

      I have copied the full working code. The return type of ‘findMaxDepth()’ is maximum of currentDepth. You can execute this program

  2. Amare Worku says:

    the index usage is not correct as the right traversal we have to increase the j not the i, and the same is true for the left. the i is index for the height and j for width.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey