aoj0092:Square Searching

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092

解法

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;
}