首页 > ACM题库 > HDU-杭电 > HDU 4495-Rectangle-计算几何-[解题报告]HOJ
2015
07-17

HDU 4495-Rectangle-计算几何-[解题报告]HOJ

Rectangle

问题描述 :

Given a rectangle which contains N rows and each of them contains a string length of M.
You must find out a symmetrical isosceles right triangle (with two equal edges and a right angle) with two edges parallel two side of the rectangle. Symmetry means the value should be the same according to the shortest altitude of the triangle. And just output the area of the triangle.

输入:

The first line of the input contains an integer T (1 <= T <= 20), which mean there are T test case follow.
For each test case, the first line contains two integer number N and M (1 <= N, M <= 500) which means described above.
And then N lines follow, which contains a string of length M. The string only contains letters or digits.

输出:

The first line of the input contains an integer T (1 <= T <= 20), which mean there are T test case follow.
For each test case, the first line contains two integer number N and M (1 <= N, M <= 500) which means described above.
And then N lines follow, which contains a string of length M. The string only contains letters or digits.

样例输入:

1 
4 4 
abab 
dacb 
adab 
cabb

样例输出:

6

题意:给出一个字符矩阵,求出字符矩阵中面积最大的对称直角等腰三角形。

         例如:

                    abg

                    bcc

                    gde   的最大结果是左上三角形,面积为6;

由于直角等腰三角形有四种朝向。(分别为直角朝左上,左下,右上,右下),所以要计算四种情况的最大值。这里只说第一种,其他三种类似,大部分代码都复用。对于求左上的,先计算出,以每个点为出发点,向右向下对称的最长长度。然后就可以枚举以每个点为对称直角等腰三角形顶点时的最大面积了。画画图比较好理解,代码如下:

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
char s[510][510];
int num1[510][510];
int num2[510][510];
int num3[510][510];
int num4[510][510];
int N,M;
void dfs1(int i,int j)
{
    int k;
    for(k=1;k+j<M&&k+i<N;k++)
        if(s[i+k][j]!=s[i][j+k])
        break;
    num1[i][j]=k-1;
}
void dfs2(int i,int j)
{
    int k;
    for(k=1;k+j<M&&i-k>=0;k++)
        if(s[i-k][j]!=s[i][j+k])
        break;
    num2[i][j]=k-1;
}
void dfs3(int i,int j)
{
    int k;
    for(k=1;j-k>=0&&i-k>=0;k++)
        if(s[i-k][j]!=s[i][j-k])
        break;
    num3[i][j]=k-1;
}
void dfs4(int i,int j)
{
    int k;
    for(k=1;j-k>=0&&k+i<N;k++)
        if(s[i+k][j]!=s[i][j-k])
        break;
    num4[i][j]=k-1;
}
int getans1(int i,int j)
{
    int k=num1[i][j];
    int ans=num1[i][j];
    for(int h=1;h<=k/2;h++)
    {
        ans=min(ans,num1[i+h][j+h]+2*h);
    }
    return ans;
}
int getans2(int i,int j)
{
    int k=num2[i][j];
    int ans=num2[i][j];
    for(int h=1;h<=k/2;h++)
    {
        ans=min(ans,num2[i-h][j+h]+2*h);
    }
    return ans;
}

int getans3(int i,int j)
{
    int k=num3[i][j];
    int ans=num3[i][j];
    for(int h=1;h<=k/2;h++)
    {
        ans=min(ans,num3[i-h][j-h]+2*h);
    }
    return ans;
}

int getans4(int i,int j)
{
    int k=num4[i][j];
    int ans=num4[i][j];
    for(int h=1;h<=k/2;h++)
    {
        ans=min(ans,num4[i+h][j-h]+2*h);
    }
    return ans;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&N,&M);
        for(int i=0;i<N;i++)
            scanf("%s",s[i]);
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
        {
            dfs1(i,j);
             dfs2(i,j);
              dfs3(i,j);
               dfs4(i,j);
        }
        int ans=0;
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
            {
                ans=max(ans,getans1(i,j));//分别为直角朝向的四个方向的计算
                ans=max(ans,getans2(i,j));
                ans=max(ans,getans3(i,j));
                ans=max(ans,getans4(i,j));
            }
            cout<<(ans+1)*(ans+2)/2<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xiefubao/article/details/18682705