The Java Program: E_square/maximumsquare.java

  1 import java.io.*;
  2 import java.util.*;
  3 
  4 public class maximumsquare 
  5 {
  6     public Scanner sc;
  7     public PrintStream ps;
  8     
  9     /**
 10      * Driver.
 11      * @throws Exception
 12      */
 13     public void doit() throws Exception
 14     {
 15         sc = new Scanner( new File( "maximumsquare.judge" ) );
 16         ps = new PrintStream( new FileOutputStream( "maximumsquare.solution" ) );
 17         
 18         int rowtotal, coltotals[], best[][];
 19         coltotals = new int[1000];
 20         best = new int[1000][1000];
 21         
 22         for(;;)
 23         {
 24             int n = sc.nextInt();
 25             int m = sc.nextInt();
 26             if( n==0 ) break;
 27             
 28             Arrays.fill( coltotals, 0 );
 29             rowtotal = 0;
 30             
 31             int bestoverall = 0;
 32             for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ )
 33             {
 34                 int element = sc.nextInt();
 35                 if( element==0 )
 36                 {
 37                     rowtotal = 0;
 38                     coltotals[j] = 0;
 39                     best[i][j] = 0;
 40                 }
 41                 else
 42                 {
 43                     if( i==0 ) rowtotal = 0;
 44                     ++rowtotal;
 45                     
 46                     if( j==0 ) coltotals[j] = 0;
 47                     ++coltotals[j];
 48                     
 49                     int prevbest = (i==0 || j==0) ? 0 : best[i-1][j-1];
 50                     
 51                     int besthere = Math.min( Math.min( rowtotal, coltotals[j] ) , prevbest+1 );
 52                     best[i][j] = besthere;
 53                     if( besthere>bestoverall ) bestoverall = besthere;
 54                 }
 55             }
 56             
 57             ps.println( bestoverall );
 58             System.out.println( bestoverall );
 59         }
 60     }
 61     
 62     /**
 63      * The main just creates an object and calls doit().
 64      * 
 65      * @param args Command line args, necessary but unused.
 66      * @throws Exception
 67      */
 68     public static void main( String[] args ) throws Exception
 69     {
 70         long start = System.currentTimeMillis();
 71         new maximumsquare().doit();
 72         long end = System.currentTimeMillis();
 73         System.out.println( "Time: " + (end-start));
 74 //        Random random = new Random();
 75 //        System.out.println( "1000 1000" );
 76 //        for( int i=0; i<1000; i++ )
 77 //        {
 78 //            for( int j=0; j<1000; j++ )
 79 //            {
 80 //                System.out.print( (j==0?"":" ") + ((random.nextFloat()<0.00001)?0:1) );   
 81 //            }
 82 //            System.out.println();
 83 //        }
 84     }
 85 
 86 }