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

川のブログ

川の適当気ままなブログです。 

AOJ 0092 Square Searching

AOJ volume0

こんにちは川です。

今回は、dpですね。

(i,j)を正方形の右下の点と置いた時の辺の長さを持っておきます。

 

ソースコード

 

#include<bits/stdc++.h>
using namespace std;
 
int dp[1000][1000];
string str[1000];
 
int serch(int n)
{
    int ans=0;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(str[i][j]=='*')dp[i][j]=0;
            else{
                if(i>0&&j>0)
           dp[i][j]=min(min(dp[i-1][j],dp[i][j-1])
                           ,dp[i-1][j-1])+1;
                else dp[i][j]=1;
                ans=max(dp[i][j],ans);
            }
        }
    }
    return ans;
}
int main()
{
    int n;
    while(cin>>n,n){
        for(int i=0;i<n;i++)cin>>str[i];
        cout<<serch(n)<<endl;
    }
}