Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

很经典到递归问题。自认为还是比较简洁到附代码

Posted by lzqxh at 2012-02-28 19:59:52 on Problem 1108
//By Lin
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; 

char	tree[1005]; 
struct	Window{
	int kind; 
	char	ch; 
	int	s1 , s2; 
	int	x , y; 
}data[2000];

int	cnt; 
int	solve( int i ,int step)
{
	if ( tree[i] >= 'A' && tree[i] <= 'Z' )
	{
		data[step].x = data[step].y = 2; 
		data[step].kind = 0; 
		data[step].ch = tree[i]; 
		return i+1; 
	}
	if ( tree[i] == '-' )  data[step].kind = 1;
	else data[step].kind = 2; 
	data[step].s1 = ++cnt; 
	data[step].s2 = ++cnt; 
	i++; 
	i = solve( i , data[step].s1 ); 
	i = solve( i , data[step].s2 );
	if ( data[step].kind == 1 )
	{
		data[step].y = max( data[data[step].s1].y , data[data[step].s2].y );
		data[step].x = data[data[step].s1].x + data[data[step].s2].x; 
	}
	else 
	{
		data[step].x = max( data[data[step].s1].x , data[data[step].s2].x );
		data[step].y = data[data[step].s1].y + data[data[step].s2].y; 
	}
	return i; 
}
char ans[1005][1005];

void	check(char &ch , char c )
{
	if ( c >='A' && c <= 'Z' ) { ch = c; return; }
	if ( ch>='A' && ch<= 'Z' ) return; 
	if ( c == '*' ) { ch = c; return; }
	if ( ch== '*' ) return; 
	ch = c; 
}
void	product(int x ,int y , int step , int p , int q)
{
	int g = p , h = q; 
	if ( data[step].kind == 0 )
	{
		check( ans[x][y] , data[step].ch ); 
		check( ans[x+g][y] , '*' );
		check( ans[x][y+h] , '*' );
		check( ans[x+g][y+h] , '*' );
		for (int i = x+1; i<x+g; i++) { check( ans[i][y] , '|' ); check( ans[i][y+h] ,'|' ); }
		for (int i = y+1; i<y+h; i++) { check( ans[x][i] , '-' ); check( ans[x+g][i] ,'-' ); }
		return; 
	}
	int s1 = data[step].s1 , s2 = data[step].s2; 
	if ( data[step].kind == 1 )
	{
		int k = p*data[s1].x/(data[s1].x+data[s2].x);
		if ( p*data[s1].x%(data[s1].x+data[s2].x) != 0 ) k++;
		product( x , y , s1 , k , q ); 
		product( x+k , y , s2 , p-k , q ); 
	}
	else
	{
		int k = q*data[s1].y/(data[s1].y+data[s2].y);
		if ( q*data[s1].y%(data[s1].y+data[s2].y) != 0 ) k++;
		product( x , y , s1 , p , k ); 
		product( x , y+k , s2 , p , q-k ); 
	}
}

int main()
{
	int cas, tt = 0; 
	scanf("%d" , &cas ); 
	while ( cas -- )
	{
		printf("%d\n" , ++ tt ); 
		scanf("%s" , tree ); 
		cnt = 0; 
		solve( 0 , 0); 
		for (int i = 0; i<=data[0].x; i++) 
			for (int j = 0; j<=data[0].y; j++) 
				ans[i][j] = ' '; 
		product( 0 , 0 , 0 , data[0].x , data[0].y ); 
		for (int i = 0; i<=data[0].x; i++) 
		{
			for (int j = 0; j<=data[0].y; j++) printf("%c" , ans[i][j] ); 
			printf("\n"); 
		}
	}
	return 0; 
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator