Counting Cells in a Sector

Problem Statement - Counting Cells in a Sector

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 25x25 grid.

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

Solution to this problem 

package test;

import java.util.Scanner;

public class CountMax {

/**

* author manish

* @param args

*/

private static int grid[][];

// static int[][] grid=new int[25][25];

private static int rows;

private static int cols;

private static final int MARKED = -1;

public static int count()

{

int maxCount=0;

int count=0;

for(int i=0;i<rows;i++)//  i

{

for(int j=0;j<cols;j++) // j

{

count=countMatrix(i,j);

//this if block to make sure that maximum node connection is returned

if(count>maxCount)

{

maxCount=count;

unmarkGrid();

}

}//for j

} //for i

return maxCount;

}

public static int countMatrix(int row,int col)

{

//if row is going out of bound

if(row<0 || row>=rows)

return 0;

//if column is going out of bound

if(col<0 || col>=cols)

return 0;

// no point looking for relations if value is not 1

if(grid[row][col]!=1)

return 0;

// if it is none of the case above then we need to check and figure out

grid[row][col]=MARKED;

int sizeofObj=1 + countMatrix(row - 1, col - 1)

+ countMatrix(row - 1, col) + countMatrix(row - 1, col + 1)

+ countMatrix(row, col - 1) + countMatrix(row, col + 1)

+ countMatrix(row + 1, col - 1) + countMatrix(row + 1, col)

+ countMatrix(row + 1, col + 1);

return sizeofObj;

}

//make it unmarked so that next time a fresh iteratio will happen and -1 will be removed from array

public static void unmarkGrid()

{

for (int i = 0; i < rows; i++)

for (int j = 0; j < cols; j++)

if (grid[i][j] == MARKED)

grid[i][j] = 1;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

// INPUT PART OF IT 

System.out.print("Enter the no of rows and columns\n");

Scanner scannerObject = new Scanner(System.in); 

rows=scannerObject.nextInt();

cols=scannerObject.nextInt();

grid = new int[rows][cols];

for(int i=0;i<rows;i++)

for(int j=0;j<cols;j++)

{

try {

// System.out.print("Enter the Digits in terms of 1 and 0\n");

grid[i][j]=scannerObject.nextInt();

// System.out.print(grid[i][j]);

} catch (NumberFormatException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

for(int i=0;i<rows;i++)

{

for(int j=0;j<cols;j++)

{

System.out.print(grid[i][j]+"\t");

}

System.out.print("\n");

}

//  CALCULATION PART OF IT 

int val=count();

   System.out.print(val);

}

}