Poj Solution 1471

http://poj.org/problem?id=1471

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
#define MAXNO 102
int tr[MAXNO][2*MAXNO-1]={0};
int maxtr[MAXNO][2*MAXNO-1]={0};
int curmax=0;
int min(int a,int b)
{
    if(a>b)
        return b;
    else
        return a;
}
int sum(int a1,int an,int n)
{
    return (a1+an)*n/2;
}
int ln(int n)
{
    return 2*n-1;
}
int mingrid(int l,int r,int d)
{
    if(d)
        return min(l,r)+1;
    else
        return 1;
    
}
int main()
{
    int N,i,j,l,r,d,di,k=1;
    int nsum,nline;
    char s[(1+MAXNO)*MAXNO/2];
    cin>>N;
    while(N)
    {
        curmax=0;
        nsum=sum(1,N,N);
        nline=ln(N);
        for(i=1;i<=N;i++)
        {
            for(j=1;j<=nline;j++)
            {
                tr[i][j]=0;
                maxtr[i][j]=0;
            }
        }
        
        for(i=1;i<=N;i++)
        {
            cin>>s;
            for(j=1;j<=ln(N-i+1);j++)
            {
                if(s[j-1]=='-')
                    tr[i][j+i-1]=1;
            }
        }

        for(i=1;i<=nline;i++)
        {
            maxtr[1][i]=tr[1][i];
            if(curmax<maxtr[1][i])
                curmax=maxtr[1][i];
        }
        if(N>1)
        {
            maxtr[N][N]=tr[N][N];
            for(i=2;i<=N;i++)
            {
                for(j=i;j<=nline-i+1;j++)
                {
                    if((j+!(i%2))%2)
                    {
                        l=maxtr[i-1][j-1];
                        r=maxtr[i-1][j+1];
                        d=tr[i-1][j];
                        if(tr[i][j])
                            maxtr[i][j]=mingrid(l,r,d);
                        if(curmax<maxtr[i][j])
                            curmax=maxtr[i][j];
                    }
                }
                di=N-i+1;
                for(j=di;j<=nline-di+1;j++)
                {
                    if((j+!(di%2))%2==0)
                    {
                        l=maxtr[di+1][j-1];
                        r=maxtr[di+1][j+1];
                        d=tr[di+1][j];
                        if(tr[di][j])
                            maxtr[di][j]=mingrid(l,r,d);
                        if(curmax<maxtr[di][j])
                            curmax=maxtr[di][j];
                    }
                }
            }
        }
        cout<<"Triangle #"<<k<<endl;
        cout<<"The largest triangle area is "<<curmax*curmax<<'.'<<endl;
        cout<<endl;
        cin>>N;
        k++;
        
    }
    
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *