1471.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#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;
}