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

October 4, 2012 4 Comments

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).

**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

** **

## Recent Comments