Counting sector from a grid

**arunk** · June 26th, 2012, 03:21 PM

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

Attached (in.txt) is the input file.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
in this i have send you my code please check it an help me to take 200 cases write now i am able to take only one case at a time.

**arunk** · June 26th, 2012, 03:29 PM

In this program i am able to read only one case so please help me out to read 200 cases as soon as posible.

**Norm** · June 26th, 2012, 03:33 PM

Please post the code you are having problems with here along with its output.
Be sure to wrap your code with
[code=java]
<YOUR CODE HERE>
[/code]
to get highlighting and preserve formatting.

**arunk** · June 26th, 2012, 03:37 PM

<package com.grid;
 
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
 
public class CountMaxSector {
	/**
	 * author arun
	 * 
	 * @param args
	 */
 
	static int rows;
	static int cols;
	static int grid[][];
	private static final int MARKED = -1;
	// declaration of arrayList
	static ArrayList<String> al = new ArrayList<String>();
 
	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(new File("D:\\data.txt"));
		while (sc.hasNext()) {
 
			al.add(sc.next());
		}// end while
		// row count
		rows = al.size();
		// column count
		cols = al.get(0).length();
		// grid declaration
		grid = new int[rows][cols];
		// nested for loop for entering data into the grid
		for (int j = 0; j < rows; j++) // j
		{
			// storing each line of data into string variable s
			String s = al.get(j);
 
			for (int k = 0, p = 0; k < cols & p < cols; p++, k++) {
				grid[j][k] = Character.getNumericValue(s.charAt(p));
				System.out.print(grid[j][k]);
			}
			System.out.println();
		}
		int val = count();
		System.out.print(val);
	}
 
	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 iteration 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;
 
	}
}>

**Norm** · June 26th, 2012, 03:39 PM

Can you post the output it creates?

**arunk** · June 26th, 2012, 03:56 PM

Input file data.txt.
Output
-----------
0101010011
1110000000
1110000111
1100001010
0100001000
0010101001
1000101001
1111100100
0110110111
0110011100
0110011111
1101111100
0000110110
0110111001
1000110001
1001101010
58

Input file input.txt
----------------------
Output
--------
200
010
111
111
110
010
001
100
111
011
011
011
110
000
011
100
100
110
001
101
111
000
111
101
100
111
101
000
010
011
111
110
010
100
100
000
010
010
010
000
001
000
000
001
111
110
101
000
000
010
111
010
111
010
001
111
011
001
010
011
001
111
011
101
010
011
011
101
001
011
000
000
101
101
100
011
010
100
001
100
101
101
110
110
111
011
001
100
001
000
101
100
101
111
110
010
100
110
000
101
011
101
100
000
010
100
011
001
010
110
111
000
100
111
000
101
100
011
011
110
010
000
000
101
011
000
000
110
000
010
000
100
010
110
100
000
111
000
101
110
000
011
001
001
010
110
100
000
111
010
011
110
000
000
001
001
010
100
000
101
101
010
011
001
010
001
001
000
011
100
100
101
001
011
010
100
010
010
111
110
001
111
111
101
001
101
000
010
010
111
101
010
001
111
011
111
001
110
011
110
001
100
110
110
000
101
000
001
100
101
101
110
101
101
100
101
010
101
001
001
000
111
011
001
101
100
011
001
011
001
000
100
001
101
000
100
011
101
001
000
100
101
100
000
000
110
001
101
001
011
100
001
010
110
111
101
111
111
110
101
000
101
011
101
111
101
010
011
110
110
001
101
011
110
001
101
111
110
011
110
001
101
111
001
010
001
111
001
011
101
101
000
011
011
010
101
110
111
100
011
000
111
111
000
000
010
100
011
001
010
010
001
110
010
011
000
100
101
111
110
111
110
111
111
001
111
110
111
110
000
100
111
111
111
111
010
011
100
100
000
111
111
100
111
001
000
000
001
010
011
000
011
110
011
110
011
111
000
001
001
010
110
101
110
110
000
011
000
111
000
011
111
001
010
011
100
110
110
011
010
101
011
011
100
010
100
101
101
010
010
011
011
111
101
101
000
101
100
011
110
111
001
001
010
101
101
001
111
001
010
111
110
100
111
011
111
111
100
011
000
010
101
001
010
000
100
101
111
001
011
100
101
010
001
010
101
001
100
010
010
100
010
101
010
111
011
011
011
000
100
001
010
111
011
101
100
010
111
110
010
110
110
111
101
000
010
010
000
111
011
010
011
001
000
000
000
001
100
100
111
011
010
001
100
011
100
000
011
001
001
101
001
110
000
101
000
010
100
110
001
001
011
010
011
011
101
011
001
001
110
110
101
011
100
011
110
101
101
100
011
110
110
101
011
100
010
001
010
010
011
000
001
000
101
001
011
011
000
011
101
100
100
111
110
100
010
000
100
100
010
100
001
110
011
011
101
001
111
000
010
010
110
011
111
010
000
001
111
000
011
110
110
111
001
111
100
011
110
010
011
000
101
010
111
100
111
011
000
011
101
010
010
011
100
111
111
010
010
110
110
101
011
011
011
000
100
110
011
011
111
101
000
010
110
101
101
001
010
110
000
001
111
111
111
111
111
001
111
100
000
101
101
001
000
101
010
111
110
110
100
101
011
100
110
001
100
110
010
010
001
000
111
101
000
110
011
000
011
001
100
101
101
010
001
100
110
011
000
110
110
110
011
011
010
100
110
111
000
001
010
100
110
000
110
000
010
110
000
100
111
011
011
000
110
100
010
111
001
110
110
111
001
111
111
111
101
111
011
001
111
010
110
011
000
111
100
110
000
000
110
011
111
000
010
101
010
110
101
010
000
001
110
111
101
010
100
011
000
010
011
011
010
001
100
100
100
000
101
100
001
000
101
101
100
101
110
111
011
000
100
101
101
011
001
110
010
001
111
001
011
001
101
111
011
011
110
101
100
110
000
111
011
110
110
001
110
111
011
001
111
011
001
110
100
110
100
111
001
000
100
110
011
111
011
101
011
000
100
011
111
001
111
011
000
110
001
111
110
000
001
101
000
001
001
110
001
100
100
000
011
010
001
000
110
101
010
100
111
011
100
101
010
111
100
110
111
110
111
111
110
100
110
110
011
011
011
011
111
000
111
001
101
001
100
101
111
100
011
011
111
111
011
010
111
010
100
100
100
001
100
111
000
011
100
011
111
101
010
111
011
110
100
001
110
010
110
011
100
010
100
101
111
001
010
011
100
010
000
010
010
101
011
000
100
010
001
100
110
001
101
110
010
101
001
010
100
011
010
011
001
111
000
111
110
111
010
001
000
010
111
010
011
110
001
000
000
010
101
111
001
011
001
000
111
011
100
001
110
010
011
000
010
101
110
100
011
011
101
101
111
001
111
001
110
010
100
111
011
010
011
010
001
111
011
011
110
110
000
010
110
100
001
110
001
011
001
001
110
011
100
010
010
001
110
111
101
000
001
011
110
001
011
101
100
011
111
100
100
001
111
100
000
011
111
000
110
010
111
001
111
111
011
110
111
000
110
100
011
001
100
001
010
000
101
001
101
000
111
110
010
000
010
001
100
010
100
111
100
110
111
110
011
111
000
000
110
001
110
001
110
110
111
110
011
101
010
100
110
110
010
100
011
001
111
110
101
011
000
111
001
101
000
011
010
100
110
000
110
011
100
011
000
110
000
110
001
010
100
000
100
110
010
101
000
010
000
011
111
011
000
000
001
011
110
011
100
011
011
100
110
100
100
111
100
100
011
100
010
101
111
010
001
100
100
000
000
011
110
011
101
100
000
100
010
100
000
100
011
000
100
011
110
100
000
110
000
110
010
111
000
001
001
100
110
111
011
001
010
111
010
010
100
000
111
101
111
000
111
100
111
110
001
011
011
010
000
101
000
111
011
011
100
101
010
010
010
111
000
011
100
110
010
101
000
111
001
100
010
001
011
110
111
110
001
100
101
000
100
011
000
110
000
010
000
000
101
000
111
111
000
111
000
001
010
011
011
011
001
000
110
001
110
110
001
010
100
011
000
010
000
111
000
010
010
110
100
100
111
011
010
110
100
100
000
011
100
111
111
011
000
100
010
100
001
000
001
111
001
010
001
110
100
100
000
100
010
110
111
100
101
101
111
000
010
011
001
000
111
000
100
110
101
110
101
011
110
110
001
001
100
000
101
010
010
110
100
000
001
111
010
011
001
111
000
100
110
110
100
010
110
010
100
000
000
000
100
000
000
110
011
010
100
111
111
011
101
010
110
111
011
011
011
001
100
110
000
101
001
100
100
110
011
010
100
010
101
001
100
001
110
010
100
101
101
000
111
010
010
111
001
000
110
110
000
111
111
010
011
000
101
011
010
001
000
010
011
010
000
001
111
011
000
010
111
001
001
110
111
101
101
000
001
011
111
101
101
011
110
111
011
110
001
011
011
111
100
010
101
101
010
011
001
000
011
001
111
011
101
110
010
101
111
011
000
101
001
111
011
000
110
011
100
001
011
001
110
001
101
001
110
100
100
110
111
001
010
110
101
011
110
100
011
100
100
011
011
011
001
111
100
001
001
100
001
101
100
101
110
111
001
100
011
000
111
000
111
101
101
110
110
101
101
101
100
011
000
001
011
100
111
101
010
001
000
011
110
110
011
011
011
000
010
011
111
000
000
110
111
110
011
110
001
101
010
000
110
110
010
010
110
110
001
110
000
100
111
101
001
100
011
100
011
001
000
111
001
110
000
000
000
011
001
110
100
101
001
101
010
010
010
001
111
011
111
101
010
011
011
000
110
001
011
000
001
100
001
111
100
010
011
000
101
011
100
100
011
011
011
011
100
110
000
111
110
001
011
001
011
011
011
001
000
000
010
000
000
011
101
011
001
001
000
000
111
001
001
011
110
010
011
111
110
100
011
101
101
000
111
111
011
110
000
101
000
010
100
011
111
100
100
011
101
010
100
110
111
100
100
010
110
100
111
001
000
100
011
111
011
110
010
100
000
110
100
000
100
110
101
001
110
101
111
010
010
100
100
100
101
110
101
101
101
110
010
010
101
010
010
011
000
100
001
011
100
010
111
001
000
101
100
011
110
001
110
010
010
000
011
101
101
111
100
010
110
010
100
111
010
011
110
000
001
001
001
001
000
110
010
011
101
001
111
100
101
011
001
010
100
000
110
111
011
011
101
110
000
111
111
111
101
111
001
110
010
010
001
010
011
011
101
010
010
100
010
110
001
011
100
110
110
110
100
010
010
111
111
011
011
101
001
110
100
110
111
101
111
101
000
010
000
101
000
101
011
101
000
001
101
010
110
100
010
011
110
011
110
000
101
010
100
100
001
001
010
001
101
101
111
011
111
110
000
000
010
110
011
011
110
100
100
111
001
010
001
101
101
001
110
011
011
010
110
001
001
111
000
000
110
110
001
110
100
010
110
011
001
110
111
011
000
000
000
111
011
101
011
010
111
001
110
111
001
101
101
011
011
001
010
011
011
011
110
101
011
011
001
110
110
101
001
000
001
100
011
001
001
101
011
011
111
111
010
001
010
011
101
000
000
000
011
110
111
110
100
011
100
111
010
011
101
101
011
010
101
001
011
111
010
110
000
110
001
001
110
111
110
011
011
101
100
010
001
101
001
000
010
011
110
001
000
010
110
101
000
000
001
100
101
010
110
100
000
111
100
011
000
001
111
010
000
011
101
000
011
100
011
011
010
010
100
100
100
011
000
101
111
111
000
001
100
000
101
001
000
010
101
100
000
100
101
011
000
011
111
111
001
111
010
011
101
000
000
100
010
110
000
011
011
110
101
100
001
010
101
111
011
001
000
110
100
000
111
100
100
101
010
101
000
001
101
000
000
011
010
010
100
111
101
100
110
101
000
001
001
000
010
001
010
111
001
011
101
100
011
111
100
111
111
000
010
010
110
111
100
100
101
001
101
010
011
010
110
110
110
111
111
001
011
010
010
000
110
111
010
000
100
101
100
111
010
010
111
001
011
001
011
111
011
001
011
001
011
110
110
111
001
000
111
111
111
011
011
001
101
011
110
100
111
101
010
101
001
110
100
110
011
011
011
001
101
001
001
111
001
101
000
100
010
100
010
001
111
110
110
000
111
110
001
001
001
011
001
000
000
101
101
010
111
111
110
101
011
101
010
110
100
001
111
100
111
011
110
011
111
111
111
011
111
000
101
111
010
101
110
100
010
001
100
001
001
010
100
001
010
100
001
011
101
011
111
001
100
011
110
010
100
111
001
011
010
010
100
101
010
100
000
111
011
001
001
111
100
000
110
011
110
011
000
000
100
011
101
111
111
111
000
011
000
100
011
000
101
100
101
100
011
011
011
100
101
001
010
111
100
110
000
111
000
011
110
010
100
001
011
000
001
100
011
010
111
111
111
001
111
111
100
111
101
011
110
000
110
110
101
111
111
110
100
000
011
100
001
011
111
000
111
011
010
110
001
010
111
010
000
000
111
100
000
010
110
010
100
001
100
000
100
101
111
110
101
100
111
101
001
100
010
110
101
010
011
000
010
111
100
100
100
011
000
110
100
011
101
100
001
101
111
011
010
100
001
100
100
011
011
011
100
101
110
011
010
110
111
111
110
100
111
101
111
111
011
000
001
101
110
110
110
101
100
000
001
001
001
011
101
101
011
101
010
000
000
001
001
111
001
110
100
110
101
110
011
000
100
010
001
001
011
110
011
101
001
000
001
011
000
110
101
100
101
000
011
100
011
011
111
101
110
011
011
000
100
011
011
110
010
110
010
100
010
010
000
001
010
111
100
011
111
011
101
010
000
011
101
100
100
100
100
111
110
011
101
110
011
001
011
011
001
100
111
111
100
100
000
111
110
100
011
111
100
011
100
111
100
011
000
111
001
000
101
101
010
101
111
101
111
011
011
110
001
010
001
111
011
001
010
101
100
000
111
010
110
101
001
000
100
011
010
111
010
111
101
001
000
010
101
001
001
011
101
011
011
111
011
000
001
000
010
011
111
101
000
000
110
111
101
010
000
010
101
111
011
100
101
111
010
110
101
111
110
111
001
100
101
001
010
101
100
011
111
001
001
000
000
110
001
010
101
101
100
011
110
111
001
011
110
111
000
111
000
110
110
111
110
011
001
001
001
000
000
001
010
001
010
011
000
001
000
001
011
000
001
110
110
110
110
010
011
011
111
001
111
110
101
000
100
110
010
001
010
010
001
111
001
010
101
101
110
001
101
001
100
010
000
111
111
101
010
111
100
110
011
011
000
111
111
000
100
010
001
000
101
101
000
111
010
111
110
010
010
101
000
000
000
000
100
110
100
000
001
000
110
101
011
011
100
000
101
111
101
000
111
110
111
111
100
001
011
100
74

**copeg** · June 26th, 2012, 04:06 PM

Please read the forum rules. I have moved this post to a more appropriate category, and your duplicate post has been deleted.

**Norm** · June 26th, 2012, 04:19 PM

Input file data.txt.
Output

What you posted makes no sense to me. One line says: input and the next line says output.
Without a clear explanation of the problem, there is no way to help.

Can you explain what the problem is with the output?

For testing you need to reduce the size of the input to a reasonable number of lines.
What you posted is way too much data to work with for testing.

**arunk** · June 26th, 2012, 11:18 PM

input.txt is the input file from where you have to take as input ,this input.txt file having 200 cases from where you have to take each case one by one.So here i am getting problem in taking multiple cases at a time.I am sending you the input file input.txt and the code which i have builded
so your job is to give me a solution that how can i take multiple cases at a time.
Below is my code and input file.

<package com.grid;
 
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
 
public class CountMaxSector {
	/**
	 * author arun
	 * 
	 * @param args
	 */
 
	static int rows;
	static int cols;
	static int grid[][];
	private static final int MARKED = -1;
	// declaration of arrayList
	static ArrayList<String> al = new ArrayList<String>();
 
	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(new File("D:\\data.txt"));
		while (sc.hasNext()) {
 
			al.add(sc.next());
		}// end while
		// row count
		rows = al.size();
		// column count
		cols = al.get(0).length();
		// grid declaration
		grid = new int[rows][cols];
		// nested for loop for entering data into the grid
		for (int j = 0; j < rows; j++) // j
		{
			// storing each line of data into string variable s
			String s = al.get(j);
 
			for (int k = 0, p = 0; k < cols & p < cols; p++, k++) {
				grid[j][k] = Character.getNumericValue(s.charAt(p));
				System.out.print(grid[j][k]);
			}
			System.out.println();
		}
		int val = count();
		System.out.print(val);
	}
 
	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 iteration 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;
 
	}
}>

**Norm** · June 27th, 2012, 06:53 AM

i am getting problem in taking multiple cases at a time

Can you define what a "case" is?
How does the program find "cases" in the input file? How many cases are there in the input file? How do you tell one case from another case?

Is the problem that the program needs a loop so that it goes back to a beginning of processing and starts again for another "case"?

Thread: Counting sector from a grid

LinkBack

Thread Tools

Display

Counting sector from a grid

Related threads:

Re: Counting sector from a grid

Re: Counting sector from a grid

The Following User Says Thank You to Norm For This Useful Post:

Re: Counting sector from a grid

Re: Counting sector from a grid

Re: Counting sector from a grid

Re: Counting sector from a grid

The Following User Says Thank You to copeg For This Useful Post:

Re: Counting sector from a grid

Re: Counting sector from a grid

Re: Counting sector from a grid

Similar Threads

Write java prgrm that determines the size of the largest sector for a given grid.

Grid bag layout inside grid bag layout

Counting cells

Help with Arrays - Counting elements

Question: counting