AOJ 0092 Square Searching
こんにちは川です。
今回は、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;
}
}