首页 > 代码库 > Uva 10593 Kites (Dp)

Uva 10593 Kites (Dp)

2024-08-02 10:10:11   221人阅读

Problem E

Kites

Time Limit

4 Seconds

 

The season of flying kites is well ahead. So what? Let us make an inventory for kites. We are given a square shaped sheet of paper. But many parts of this are already porous. Your challenge here is to count the total number of ways to cut a kite of any size from this sheet. By the way, the kite itself can‘t be porous :-) AND..................it must be either square shaped or diamond shaped.

 
                        x
           x           xxx           xxx           xxx
          xxx         xxxxx          xxx           x.x         x
           x           xxx           xxx           xxx
                        x

In the above figure first three are valid kites but not next two.

 

Input

Input contains an integer n (n ≤ 500), which is the size of the sheet. Then follows n lines each of which has n characters (‘x‘ or ‘.‘). Here the dotted parts resemble the porous parts of the sheet. Input is terminated by end of file.

 

Output

Output is very simple. Only print an integer according to the problem statement for each test case in a new line.

 

Sample Input

Output for Sample Input

4
.xx.
xxxx
.xx.
.x..
3
xxx
xxx
xxx

4

6

 

题意：给你一个 n*n的表，让你在表中找出x组成的边长大于等于2的菱形或正方

形（必须完全填充）的数目。

思路： dp[i][j]表示以(i,j)点为右下角，所形成的图形的最大边长.

对于正方形，如下图 ：


 w = min(dp[i][j-1],dp[i-1][j]);  

当  G[ i - w ][ j - w ] == x（图中打叉位置） 时  ：  dp[ i ][ j ] = w+1;

 否则   dp[ i ][ j ] = max( w , 1 );


对于菱形，如下图 ：


分析同上


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=510;

int dp1[maxn][maxn],dp2[maxn][maxn],n,ans;
char G[maxn][maxn];

void initial()
{
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
}

void input()
{
    for(int i=0; i<n; i++)
    {
        getchar();
        scanf("%s",G[i]);
    }
}

void solve()
{
    ans=0;
    for(int i=0; i<n; i++)
    {
        if(G[0][i]=='x') dp1[0][i]=dp2[0][i]=1;
        if(G[i][0]=='x') dp1[i][0]=dp2[i][0]=1;
        if(G[i][n-1]=='x')  dp2[i][n-1]=1;
    }

    for(int i=1; i<n; i++)
    {
        for(int j=1; j<n; j++)
            if(G[i][j]=='x')
            {
                int w=min(dp1[i-1][j],dp1[i][j-1]);
                if(G[i-w][j-w]=='x') dp1[i][j]=w+1;
                else dp1[i][j]=max(w,1);

                ans+=dp1[i][j]-1;

                if(j!=n-1)
                {
                    if(G[i-1][j]=='.')  dp2[i][j]=1;
                    else
                    {
                        w=min(dp2[i-1][j-1],dp2[i-1][j+1]);
                        if(i>=2*w && G[i-2*w][j]=='x' && G[i-2*w+1][j]=='x') dp2[i][j]=w+1;
                        else dp2[i][j]=max(w,1);
                    }
                    ans+=dp2[i][j]-1;
                }
            }
    }
    printf("%d\n",ans);
}


int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        initial();
        input();
        solve();
    }
    return 0;
}


Uva 10593 Kites (Dp)


联系
我们