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
11
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
64
65
66
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
75
76
77
78
79
80
81
82
83
84 }
85
86 }