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