The Java Program: Square.java

  1 /*
  2   Southeast USA, 2010. Problem E: Maximum Square
  3   Categories: dynamic programming
  4  */
  5 import java.io.*;
  6 import java.util.Scanner;
  7 
  8 public final class Square {
  9 
 10    private static final Scanner STDIN =
 11       new Scanner (new BufferedInputStream (System.in));
 12 
 13    public static void main (final String[] args) {
 14       input: for (int ds=1; /**/; ds++) {
 15          final int n = STDIN.nextInt();  // rows
 16          final int m = STDIN.nextInt();  // cols
 17          if (n==0 || m==0) break;
 18          assert 1<=n && n<=1000;
 19          assert 1<=m && m<=1000;
 20 
 21          // square[r][c] is the largest square of all 1's with
 22          // lower, left corner at (r,c)
 23          final int[][]square = new int[n][m];
 24 
 25          int max=0;
 26 
 27          for (int row=0; row<n; row++) {
 28             for (int col=0; col<m; col++) {
 29                final int a = STDIN.nextInt();
 30                assert a==0 || a==1;
 31 
 32                if (row==0 || col==0 || a==0 || square[row-1][col]==0 || square[row][col-1]==0) {
 33                   square[row][col]=a;
 34                } else {
 35                   final int x = Math.min (square[row-1][col], square[row][col-1]);
 36                   //                  square[row][col] = square[row-x][col-x]>0 ? x+1 : x;
 37                   square[row][col] = square[row-1][col-1]>=x ? x+1 : x;
 38 
 39                }
 40                assert 0<=square[row][col];
 41                if (square[row][col]>max) max=square[row][col];
 42             }
 43          }
 44          System.out.println (max);
 45       }
 46    }
 47 }
 48 
 49 /*
 50  * ------------For GNU Emacs ------------
 51  * Local Variables:
 52  * compile-command: "javac Square.java"
 53  * End:
 54  */