UVa 10593 : Kites

問題リンク : http://uva.onlinejudge.org/external/105/10593.pdf

問題概要 :
n * n の char のシートが与えられる
それに含まれる要素は 'x' か '.' のいずれか
この中に含まれる大きさが１より大きい正方形とダイアモンドの数を数えよ

解法 :
動的計画法
正方形については以下のようにして数えることができる
dp[i][j] := (j,i) を右下とする正方形の最大の大きさ
dp[i][j] = min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1] ) + 1
ただし範囲外の場合はそのdpの値は0とする
その座標を右下とする正方形の最大の大きさがわかれば、
同様にしてそこを右下とする正方形の数は ( 最大値 - 1 ) となる

ダイアモンドについては次の通り
dp[i][j] := (j,i)をダイアモンドの一番下の角とするダイアモンドの最大の大きさ
dp[i][j] = min( dp[i-1][j-1], dp[i-1][j+1], dp[i-2][j] ) + 1
ただし、範囲外のdpは０
尚且つ (j,i-1) が 'x' でない場合はダイアモンドにはならないので dp[i][j] は 1 となる
これも正方形と同様で、最大の大きささえわかればそこからできるものの数は ( 最大値 - 1 ) である

O(n^2)

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

char a[501][501];
int n,dp[501][501][2]; // 0 -> diamond, 1 -> square

inline bool isValid(int x,int y) { return 0 <= x && x < n && 0 <= y && y < n; }

int main(){
  while( scanf("%d",&n) != EOF ){
    rep(i,n) rep(j,n) scanf(" %c",&a[i][j]);
    int cnt = 0;
    rep(i,n) rep(j,n) {
      if( a[i][j] == 'x' ) {
        int mini = INT_MAX;
        mini = min(mini,isValid(j-1,i-1)?dp[i-1][j-1][0]:0);
        mini = min(mini,isValid(j+1,i-1)?dp[i-1][j+1][0]:0);
        mini = min(mini,isValid(j  ,i-2)?dp[i-2][j  ][0]:0);
        if( isValid(j,i-1) && a[i-1][j] == 'x' ) dp[i][j][0] = mini + 1;
        else                                     dp[i][j][0] = 1;

        mini = INT_MAX;
        mini = min(mini,isValid(j-1,i-1)?dp[i-1][j-1][1]:0);
        mini = min(mini,isValid(j-1,i  )?dp[i  ][j-1][1]:0);
        mini = min(mini,isValid(j  ,i-1)?dp[i-1][j  ][1]:0);
        dp[i][j][1] = mini + 1;
      } else dp[i][j][0] = dp[i][j][1] = 0;
      cnt += ( ( ( dp[i][j][0] >= 2 ) ? dp[i][j][0]-1 : 0 ) + ( ( dp[i][j][1] >= 2 ) ? dp[i][j][1]-1 : 0) );
    }
    printf("%d\n",cnt);
  }
  return 0;
}