1467 triangles.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

#include <cstdio>
#include <string>
using namespace std;
char map[101][201];
int line[201];
int n;

inline int nmin(int a,int b)
{
	if(a>b)
		return b;
	else
		return a;
}

int down()
{
	int i,j,best;
	
	memset(line,0,sizeof(line));
	
	best=0;
	for(i=0 ;i<2*n-1; i+=2)
		if(map[0][i] =='-') 
			best= line[i]= 1; 
		else 
			line[i]= 0;
			
	for(i=1 ;i<n; i++)
	{
		for(j=0 ;j<2*(n-i)-1; j+=2)
			if(map[i][j] =='-')
			{
				if(map[i-1][j+1] =='-')
				    line[j]= 1+ nmin( line[j],line[j+2] );
				else
				    line[j]= 1;
    			if(line[j]>best)
					best=line[j];
			}
			else 
				line[j]= 0;
	}
			
	return best;
}

int up()
{
	int i,j,best;
	
	memset(line,0,sizeof(line));
	best=0;
	for(i=n-2;i>=0;i--)
    {
		for(j=2*(n-i)-3;j>=1;j-=2)
			if(map[i][j] == '-')
			{
				if(map[i+1][j-1] == '-' && j > 1 && j < (2*(n-i)-3))
					line[j] = 1+ nmin( line[j-2],line[j]);
			    else
					line[j] = 1;
				if(line[j]>best)
					best=line[j];
			}
			else 
				line[j] = 0;
    }
			
    return best;
}

int main()
{
	int i,j,ans,t;
	
	t=0;
	while( scanf("%d",&n)!=EOF && n)
	{
		t++;
		for(i=0;i<n;i++)
			scanf("%s",map[i]);
		
		ans=down();
		j=up();
		if(ans<j)
			ans=j;
			
		printf("Triangle #%d\nThe largest triangle area is %d.\n\n",t,ans*ans);
	}
	return 0;
}