読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

aoj0092:Square Searching

解法

dp[i+1][j+1]:(i,j)を右下の頂点とする正方形のなかで辺の長さが最大であるようなものの辺の長さ、とする。

ここで、例えば(i,j)を右下として辺の長さが3の正方形を作れるときは、(i-1,j-1),(i-1,j),(i,j-1)を右下とする辺の長さ2の正方形がそれぞれ作れる。

また、(i-1,j-1),(i-1,j),(i,j-1)を右下とする最大の正方形の辺の長さがそれぞれ2,4,3だとすると、(i,j)を右下とする最大の正方形の辺の長さは3である。

これより、

dp[i+1][j+1]=min(dp[i][j],dp[i-1][j],dp[i][j-1])

という漸化式が成り立つことがなんとなくわかる。



コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(scanf("%d",&n),n){
        int dp[2][1010]={{0}};
        int ma=0;
        for(int i=0;i<n;i++){
            char str[1010];
            scanf("%s",str);
            for(int j=0;j<n;j++){
                if(str[j]=='*')dp[(i+1)&1][j+1]=0;
                else{
                    dp[(i+1)&1][j+1]=min(dp[i&1][j],min(dp[(i+1)&1][j],dp[i&1][j+1]))+1;
                }
                ma=max(ma,dp[(i+1)&1][j+1]);
            }
        }

        printf("%d\n",ma);
    }

    return 0;
}