Aizu Online Judge 0092 Square Searching

■0092 Square Searching

dp[j][i] := (i,j)が右下となる正方形の最大辺

とすると，dp[j][i]を決めるには，(i,j)の左上，左，上を見れば良い．n = min{dp[j-1][i-1], dp[j][i-1], dp[j-1][i]}とすると，(i,j)を右下とする長さn+1の正方形内は全て空白となる．即ち，

dp[j][i] = min{dp[j-1][i-1], dp[j][i-1], dp[j-1][i]} + 1

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n;  
17.  int[][] a;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    if(n==0){  
23.     break;  
24.    }  
25.    a=new int[n][n];  
26.    for(int j=0; j<n; j++){  
27.     String s=sc.next();  
28.     for(int i=0; i<n; i++){  
29.      a[j][i]=s.charAt(i)=='.'?0:1;  
30.     }  
31.    }  
32.    solve();  
33.   }  
34.  }  
35.   
36.  void solve(){  
37.   int[][] dp=new int[n][n];  
38.   int max=0;  
39.   for(int j=0; j<n; j++){  
40.    for(int i=0; i<n; i++){  
41.     if(a[j][i]==0){  
42.      if(i>0&&j>0){  
43.       int n=Math.min(dp[j-1][i-1],  
44.         Math.min(dp[j][i-1], dp[j-1][i]));  
45.       dp[j][i]=n+1;  
46.      }else{  
47.       dp[j][i]=1;  
48.      }  
49.     }else{  
50.      dp[j][i]=0;  
51.     }  
52.     max=Math.max(max, dp[j][i]);  
53.    }  
54.   }  
55.   println(""+max);  
56.  }  
57.   
58.  void debug(Object... os){  
59.   System.err.println(Arrays.deepToString(os));  
60.  }  
61.   
62.  void print(String s){  
63.   System.out.print(s);  
64.  }  
65.   
66.  void println(String s){  
67.   System.out.println(s);  
68.  }  
69.   
70.  public static void main(String[] args){  
71.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
72.   new Main().run();  
73.  }  
74. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[][] a;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   a=new int[n][n];
   for(int j=0; j<n; j++){
    String s=sc.next();
    for(int i=0; i<n; i++){
     a[j][i]=s.charAt(i)=='.'?0:1;
    }
   }
   solve();
  }
 }

 void solve(){
  int[][] dp=new int[n][n];
  int max=0;
  for(int j=0; j<n; j++){
   for(int i=0; i<n; i++){
    if(a[j][i]==0){
     if(i>0&&j>0){
      int n=Math.min(dp[j-1][i-1],
        Math.min(dp[j][i-1], dp[j-1][i]));
      dp[j][i]=n+1;
     }else{
      dp[j][i]=1;
     }
    }else{
     dp[j][i]=0;
    }
    max=Math.max(max, dp[j][i]);
   }
  }
  println(""+max);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}