AOJ0092 Square Searching

AOJ Volume0

問題リンク Square Searching

  • 解法

右下の座標が(i,j)で1辺がwの正方形が作れるかは下準備をすればO(1)で判定できます。
sum[i][j]という2次元配列を用意します。これは(0,0)〜(i,j)の長方形に含まれる空きマスの数を表します。
このsumを使うとマップ上の任意の長方形に含まれる空きマスの数が分かります。
特に今回は正方形を調べるので、右下の座標(i,j)で1辺がwの正方形に含まれる空きマスSは
S = sum[i][j]-sum[i-w][j]-sum[i][j-w]+sum[i-w][j-w]
であるのでSがw*wと等しければその正方形が作れます。
あとは正方形の幅をnから徐々に落として行って、その幅を持つ正方形がどこかに作れるかを全て調べれば解けます。

計算量は下準備にO(n^2)
正方形の幅のループO(n)に対して正方形を作れる場所を探すのにO(n^2)なのでO(n^3)になると思います。

  • ソース
import java.util.Scanner;

//Square Searching
public class AOJ0092 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			int[][] a = new int[n][n];
			int[][] sum = new int[n+1][n+1];
			for(int i=0;i<n;i++){
				char[] s = sc.next().toCharArray();
				for(int j=0;j<n;j++)a[i][j]=s[j]=='.'?1:0;
			}
			sum[1][1] = a[0][0];
			for(int i=2;i<=n;i++){
				sum[1][i] = a[0][i-1]+sum[1][i-1];
				sum[i][1] = a[i-1][0]+sum[i-1][1];
			}
			for(int i=2;i<=n;i++){
				for(int j=2;j<=n;j++){
					sum[i][j] = a[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
				}
			}
			int max = 0;
			for(int k=1;k<=n;k++){
				boolean f = false;
				for(int i=k;i<=n;i++){
					for(int j=k;j<=n;j++){
						if(sum[i][j]-sum[i-k][j]-sum[i][j-k]+sum[i-k][j-k]==k*k){
							f = true;
							break;
						}
					}
					if(f)break;
				}

				if(f){
					max = k;
				}
				else break;
			}
			System.out.println(max);
		}
	}
}