首页 > ACM题库 > HDU-杭电 > HDU 1510 White Rectangles-动态规划-[解题报告] C++
2013
12-12

HDU 1510 White Rectangles-动态规划-[解题报告] C++

White Rectangles

问题描述 :

You are given a chessboard made up of N squares by N squares with equal size. Some of the squares are colored black, and the others are colored white. Please write a program to calculate the number of rectangles which are completely made up of white squares.

输入:

There are multiple test cases. Each test case begins with an integer N (1 <= N <= 100), the board size. The following N lines, each with N characters, have only two valid character values:

# – (sharp) representing a black square;
. – (point) representing a white square.

Process to the end of file.

输出:

For each test case in the input, your program must output the number of white rectangles, as shown in the sample output.

样例输入:

2
.#
..
4
..#.
##.#
.#..
.#.#

样例输出:

5
15

又一DP

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=110;
char A[maxn][maxn];
int a[maxn][maxn];
int main()
{
    int T;
    int sum;
    while (cin>>T){
        getchar();
        sum=0;
        memset(a,0,sizeof(a));
        for(int i=0;i<T;i++){
            gets(A[i]);
            int l=strlen(A[i]);
            for(int j=0;j<l;j++){
                if(A[i][j]=='#') a[i][j]=0;
                else if(!i) a[i][j]=1;
                else a[i][j]=a[i-1][j]+1;
                sum+=a[i][j];
                if(j){
                    int ans=a[i][j];
                    for(int x=j-1;x>=0;x--){
                        if(!a[i][x]) break;
                        ans=min(ans,a[i][x]);
                        sum+=ans;
                    }
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/qzh3578/article/details/16804055