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

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0092

algorithm algorithm-動的計画法 contest contest-aoj language language-c++

正方形探索 | Aizu Online Judge
動的計画法の問題.
dp(i,j)を(i,j)を右下の頂点とするの最大サイズと定義し以下のような漸化式を計算すれば良い.

  • dp(i,j) = min(dp(i-1,j),dp(i-1,j-1),dp(i,j-1))+1

あとは最大値を求めればよい.

int main()
{
  string s;
  int n;
  while(cin >> n,n)
  {
    vector<int> dp(n*n,0);
    REP(i,n)
    {
      cin>>s;
      REP(j,n) if(s[j]=='.') dp[i*n+j] = 1;
    }
    FOR(i,1,n-1) FOR(j,1,n-1) if(dp[i*n+j])
      dp[i*n+j]=min({dp[(i-1)*n+j],dp[(i-1)*n+(j-1)],dp[i*n+(j-1)]})+1;
    cout << *max_element(dp.begin(),dp.end()) << endl;
  }
  return 0;
}