Competitive Programming: USACO Big Barn

by Paul Epps on 16 Apr 2018

Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis.

EXAMPLE

Consider the following grid of Farmer John’s land where ‘.’ represents a parcel with no trees and ‘#’ represents a parcel with trees:

          1 2 3 4 5 6 7 8
        1 . . . . . . . .
        2 . # . . . # . .
        3 . . . . . . . .
        4 . . . . . . . .
        5 . . . . . . . .
        6 . . # . . . . .
        7 . . . . . . . .
        8 . . . . . . . .

The largest barn is 5 x 5 and can be placed in either of two locations in the lower right part of the grid.

PROGRAM NAME: bigbrn

INPUT FORMAT

Line 1:	Two integers: N (1 <= N <= 1000), the number of parcels on a side, and T (1 <= T <= 10,000) the number of parcels with trees
Lines 2..T+1:	Two integers (1 <= each integer <= N), the row and column of a tree parcel

SAMPLE INPUT (file bigbrn.in)

OUTPUT FORMAT

The output file should consist of exactly one line, the maximum side length of John’s barn.

SAMPLE OUTPUT (file bigbrn.out)

Solution below . . .

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/*
 * ID: paul9
 * LANG: JAVA
 * TASK: bigbrn
 * 
 * Dynamic programming solution: 
 * 
 * Initialize another matrix (dp) with the same dimensions as the original.
 * dp(i,j) represents the side length of the maximum square whose bottom 
 * right corner is the cell with index (i,j) in the original matrix.
 * 
 * Starting from index (1,1), for every '.' found in the original matrix, 
 * update the value of the current element as
 * 
 *   dp(i, j) = min ( dp(i-1, j), dp(i-1, j-1), dp(i, j-1) ) + 1. 
 * 
 * We also remember the size of the largest side length found so far. 
 * In this way, we traverse the original matrix once and find the maximum 
 * side length.
*/

class bigbrn {

	static int maximalSquare(char[][] matrix) {
		int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
		int[][] dp = new int[rows + 1][cols + 1];
		int maxsqlen = 0;
		for (int i = 1; i <= rows; i++) {
			for (int j = 1; j <= cols; j++) {
				if (matrix[i - 1][j - 1] == '.') {
					dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
					maxsqlen = Math.max(maxsqlen, dp[i][j]);
				}
			}
		}
		return maxsqlen;
	}

	public static void main(String[] args) throws IOException {
		long start = System.currentTimeMillis();
		Scanner sc = new Scanner(new File("bigbrn.in"));
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("bigbrn.out")));

		int N = sc.nextInt();
		int T = sc.nextInt();

		char[][] grid = new char[N][N];

		// initialize the grid
		for (int i = 0; i < grid.length; i++) {
			char[] row = new char[N];
			Arrays.fill(row, '.');
			grid[i] = row;
		}

		for (int i = 0; i < T; i++) {
			// converting from 1-based to 0-based
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;

			grid[x][y] = '#';
		}

		sc.close();

		out.println(maximalSquare(grid));
		out.close();

		System.out.println("$:" + (System.currentTimeMillis() - start));

	}
}

← Competitive Programming: POJ 1654 – Area

Where it Went →