１辺がn枡の正方形の升目がある。各升目は黒、あるいは白で塗られている。
白い升目のみから成る、最大の正方形の一辺の長さを求めたい。
効率のよい算法を示せ。時間、空間計算量について論ぜよ。
---------------------
/*
入力の正方形は、一辺をN, 黒は0, 白は1として、(i,j)升目の色がrect[i][j]で得られるものとする。
解 時間O(N^2), 作業領域O(N)，
右下角の升目座標を(i,j)とする白い正方形の最大の一辺の長さをsol(i,j) とすると、
sol(i,j) = min (sol(i-1,j), sol(i,j-1), sol(i-1,j-1)) + 1
との再帰式が成り立つ。
solをそのまま配列で作成すると、O(N^2)の作業領域を必要とする。
が、実際に必要なのは、直前の列と、sol(i,j-1)のみであることから、作業領域はO(N)で済む。
*/
class Solve0 extends Solve{
int memo[] = new int[N];
int memo_mae[] = new int[N];
void exec(){
int max = 0;
for(int j = 0; j < N; j++){
memo_mae[j] = rect[0][j];
}
for(int i = 1; i < N; i++){
memo[0] = rect[i][0];
for(int j = 1; j < N; j++){
if(rect[i][j] > 0){
memo[j] = Math.min(Math.min(memo_mae[j],memo_mae[j-1]),
memo[j-1])+1;
}
else{
memo[j] = 0;
}
/* 最大値を更新 */
if(max < memo[j]){
max = memo[j];
}
}
/*覚えておきたいものをコピー*/
for(int j = 0; j < N; j++){
memo_mae[j] = memo[j];
}
}
System.out.println("Result of Solve0:"+max);
}
}
/*
別解: 時間O(N^2), 作業領域O(N)
1.列ごとに、白い升目が連続する数を集計。
例 1 1 0 1 1 0
0 1 1 => 0 2 1
1 1 1 1 3 2
2.行ごとに1の結果を見て、max値以上の数がmax回連続すれば、そこに一辺がmax の正方形が存在する。
たとえば、上右図第3行は、2と3が連続するため、1辺が2の正方形が存在することがわかる。
プログラムは、上の1と2を同時に行うことにより、作業領域をO(N)に抑えたもの。
*/
class Solve1 extends Solve{
int memo[] = new int[N];
int memo_mae[] = new int[N];
int num = 0; /*上の2を実行する際に、連なり数をとっておく*/
int max = 0;
void exec(){
for(int i = 0; i < N; i++){
num = 0;
for(int j = 0; j < N; j++){
/* 縦に1が続く数を積算*/
if(rect[i][j] == 1){
if(i == 0)memo[j] = 1;
else
memo[j] = memo_mae[j]+1;
}
else{
memo[j] = 0;
}
/*
max+1を超える値が、max+1回続くかどうかを調べる。
もし、maxの大きさの正方形があれば、必ず前の行で
調べられているはずだから、max+1だけ調べればよい。
*/
if(memo[j] > max){
num++;
}
else{
num = 0;
}
if(num > max){
max++;
}
/*覚えておきたいものをコピー*/
memo_mae[j] = memo[j];
}
}
System.out.println("Result of Solve1:"+max);
}
}
/*
全升目をスキャンしなければならない以上、最低の計算量はO(N^2)である。
したがって、上の解の時間上の計算量は、いずれも、漸近的に最良解を与える。
*/
back