首页 > 代码库 > uva 10593 - Kites(dp)

uva 10593 - Kites(dp)

题目链接:uva 10593 - Kites

题目大意:给出一个n*n的图,表示一张纸板,问有多少种方法做成风筝,风筝必须是正方形或者是菱形,并且不能有洞。

解题思路:分正方形和菱形两种情况讨论:

  • 正方形,dp[i][j]表示以i,j为右下角的正方形
    dp[i][j]=min(dp[i?1][j],dp[i][j?1])
    并且如果黄色部分也为‘x‘的话,dp[i][j]++


  • 菱形,dp[i][j]表示菱形的正下角

    同样地市黄色部分如果为’x‘的话,dp[i][j]++


#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 505;

int n, dp[N][N];
char g[N][N];

int solve () {
    int ans = 0;
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] == ‘x‘) {
                int tmp = min(dp[i-1][j], dp[i][j-1]);
                dp[i][j] = tmp + (g[i-tmp][j-tmp] == ‘x‘);

                if (dp[i][j] > 1)
                    ans += dp[i][j] - 1;
            }
        }
    }

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] == ‘x‘) {
                int tmp = min(dp[i-1][j-1], dp[i-1][j+1]);

                if (tmp == 0 || g[i-1][j] != ‘x‘)
                    dp[i][j] = 1;
                else if (g[i-tmp*2][j] == ‘x‘ && g[i-tmp*2+1][j] == ‘x‘)
                    dp[i][j] = tmp + 1;
                else
                    dp[i][j] = tmp;

                if (dp[i][j] > 1)
                    ans += dp[i][j] - 1;
            }
        }
    }
    return ans;
}

int main () {
    while (scanf("%d%*c", &n) == 1 && n) {
        for (int i = 1; i <= n; i++)
            gets(g[i]+1);
        printf("%d\n", solve());
    }
    return 0;
}