Final: Biggest Empty Plot

Lab Java Advanced 30 points

A map of land is a grid of 1 (free) and 0 (built on). Find the side length of the biggest square made only of free cells. DP idea: the biggest square whose bottom-right corner is a free cell is 1 + the smallest of the squares ending just above, just left, and diagonally up-left.

Input

Line 1: rows cols. Then rows lines of 0s and 1s (no spaces).

Output

The side length of the biggest free square.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

dp[r][c] = side of the biggest free square whose bottom-right corner is (r, c).

A free cell: 1 + min(above, left, up-left). A built cell: 0.

Solution explanation

One pass over the grid: O(rows × cols). Checking every possible square directly would be far slower.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int rows = sc.nextInt(), cols = sc.nextInt();
        int[][] dp = new int[rows + 1][cols + 1];      // extra row and column of zeros
        int best = 0;
        for (int r = 1; r <= rows; r++) {
            String line = sc.next();
            for (int c = 1; c <= cols; c++) {
                if (line.charAt(c - 1) == '1') {
                    dp[r][c] = 1 + Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1]));
                    best = Math.max(best, dp[r][c]);
                }
            }
        }
        System.out.println(best);
    }
}

Output

Answer