| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
很经典到递归问题。自认为还是比较简洁到附代码//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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator