CS1020 Land Lab1 Ex2

Link to the question – Land Lab 1 Ex 2

import java.util.*;

class Tree {
	int x;
	int y;
	public Tree(int x, int y)
	{
		this.x = x;
		this.y = y;
	}
}

class Grid {

    // declare the member field

    // declare the constructor

	/**
	 *	   checkNoTree   : to check whether the (size x size) square with upper-left coordinate 
	 *                     (x, y) contains a tree
	 *	   Pre-condition :
	 *	   Post-condition:
	 */
	public boolean checkNoTree(int x, int y, int size) {
		
		return false;
	}



	/**
	 *	   checkValidSize: to check whether it is possible to find a (size x size) square that contains 
	 *                     no tree
	 *	   Pre-condition :
	 *	   Post-condition:
	 */
	public boolean checkValidSize(int size) {
		
		return false;
	}



	/** 
	 *	   solve         : use this method to find the largest size of a square with no trees
	 *	   Pre-condition :
	 *	   Post-condition:
	 */
	public int solve() {
		
		return 0;
	}

}

class Land {

	public static void main(String[] args) {

		// declare the necessary variables

		// create new object from class Result

		// declare a Scanner object to read input
		Scanner sc = new Scanner(System.in);
		// read input and process them accordingly
		int sizeOfArray = sc.nextInt();
		if(sizeOfArray >= 1 || sizeOfArray <= 80)
		{
			int[][] listOfTrees = new int[sizeOfArray][sizeOfArray];
			int numberOfTrees = sc.nextInt();
			if(numberOfTrees >= 1 || numberOfTrees <= 500)
			{
				for(int i = 0; i < sizeOfArray; i++)
				{
					for(int j = 0; j < sizeOfArray; j++)
					{
						listOfTrees[i][j] = 1;
					}
				}
				//collect the coord of the trees
				for(int i = 0; i < numberOfTrees; i++)
				{
					int x = sc.nextInt();
					int y = sc.nextInt();
					listOfTrees[x-1][y-1] = 0; // 0 indicate a tree, 1 indicate empty land
				}
				System.out.println(squareTest(listOfTrees, sizeOfArray));
			}
			else
			{
				return;
			}
		}
		else
		{
			return;
		}
	}
	
	public static int squareTest(int[][] square, int size)
	{	
		int max = 0;
        	for (int row=0; row<size; row++)
        	{
            		for (int col=0; col<size; col++)
            		{
           		 	if (row==0 || col==0 || square[row][col]==0 || square[row-1][col]==0 || square[row][col-1]==0)	//set col 0 and row 1 as it is.
            			{
            				square[row][col]=square[row][col];
            			}
            			else
            			{
            				int min = Math.min (square[row-1][col], square[row][col-1]); //traverse from bottom right up to top left. moving row-1, col-1 at each time, returning the smaller of the two
            				if(square[row-1][col-1] >= min)
            				{
            					min++;
            				}
            				square[row][col] = min;	//save the value into the array
            			}
            			if(square[row][col]>max)	//check if the value in the array is the largest
				{
					max=square[row][col];
				}
            		}
		}
		return max;
	}
}
Advertisements
This entry was posted in NUS, SoC and tagged , . Bookmark the permalink.

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