题目描述:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=43
算法分析:
纯粹大模拟, 考验编码能力, 我写了120+行...
前序表达式还好 ... 中间要注意不断向前调整大小, 最后根据调整后的大小输出结果.
zoj 1043
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<string>
5 #include<vector>
6 using namespace std;
7 char ch[100];int now;
8 pair<int,int> tree[100], sz[100];
9 void split(int &l,int &r,int all){
10 // cout<<"split: "<<l<<" "<<r<<" "<<all<<endl;
11 int L = int(1.0*l/(l+r)*all+1e-8);
12 int R = int(1.0*r/(l+r)*all+1e-8);
13 if(L + R < all) L++;
14 l =L, r = R;
15 }
16 void work(int p,int h,int w){
17 // cout<<"work: "<< p <<" "<<h<<" "<<w<<endl;
18 char c = ch[p];
19 if(sz[p].first == h && sz[p].second == w)
20 return ;
21 sz[p] = make_pair(h,w);
22 if(c >= 'A' && c <= 'Z'){
23 return ;
24 }
25 int L = tree[p].first, R = tree[p].second;
26 if(c == '|') {
27 int lw = sz[L].second, rw = sz[R].second;
28 split(lw, rw, w);
29 work(L, h, lw);
30 work(R, h, rw);
31 }
32 else {
33 int lh = sz[L].first, rh = sz[R].first;
34 split(lh, rh, h);
35 work(L, lh, w);
36 work(R, rh, w);
37 }
38 }
39 void dfs(int p) {
40 now++;
41 char c = ch[p];
42 if(c >= 'A' && c <= 'Z') {
43 sz[p] = make_pair(2,2);
44 return;
45 }
46 int L = (tree[p].first = now);
47 dfs(now);
48 int R = (tree[p].second = now);
49 dfs(now);
50 if(c == '|') {
51 int H = max(sz[L].first, sz[R].first);
52 work(L, H, sz[L].second );
53 work(R, H, sz[R].second );
54 sz[p] = make_pair(H, sz[L].second + sz[R].second);
55 }
56 else {
57 int W = max(sz[L].second, sz[R].second);
58 work(L,sz[L].first ,W);
59 work(R,sz[R].first ,W);
60 sz[p] = make_pair(sz[L].first + sz[R].first, W);
61 }
62 // cout<<p<<" "<<sz[p].first <<" "<<sz[p].second <<endl;
63 }
64 const int N = 80;
65 inline void cal(char &a,char b){
66 if(b == '|' || b == '-') return ;
67 a = b;
68 }
69 void output(char t[][N], int p) {
70 char c = ch[p];
71 int w = sz[p].second, h = sz[p].first;
72 if(c <= 'Z' && c >= 'A'){
73 t[0][0] = c;
74 for(int j = 1; j < w; j++)
75 t[0][j] = '-';
76 t[0][w] = '*';
77 for(int i = 1; i < h ; i++){
78 t[i][0] = ('|');
79 for(int j = 1; j < w; j++){
80 t[i][j] = (' ');
81 }
82 t[i][w] = ('|');
83 }
84 t[h][0] = '*';
85 for(int j = 1; j < w; j++)
86 t[h][j] = '-';
87 t[h][w] = '*';
88 return ;
89 }
90 int l = tree[p].first, r = tree[p].second;
91 char s[N][N];
92 output(t,l);
93 output(s,r);
94 if(c == '-') {
95 for(int j = 0; j <= w; j++)
96 cal(t[sz[l].first][j],s[0][j]);
97 for(int i = sz[l].first+1; i <= h; i++){
98 for(int j = 0; j <= w; j ++)
99 t[i][j] = s[i-sz[l].first][j];
100 }
101 }
102 else {
103 for(int i =0; i <=h; i++)
104 cal(t[i][sz[l].second],s[i][0]);
105 for(int i = 0; i <= h; i++)
106 for(int j = sz[l].second+1; j <=w; j++)
107 t[i][j] = s[i][j - sz[l].second];
108 }
109 }
110 char ans[N][N];
111 int main(){
112 int cas;
113 cin >> cas;
114 for(int oo = 1; oo <= cas; oo ++){
115 now = 0;
116 scanf("%s",ch);
117 dfs(0);
118 output(ans,0);
119 cout << oo << endl;
120 for(int i = 0; i <= sz[0].first; i++){
121 for(int j = 0; j <= sz[0].second; j ++)
122 printf("%c", ans[i][j]);
123 printf("\n");
124 }
125 }
126 }
127 posted on 2012-09-04 20:41
西月弦 阅读(195)
评论(0) 编辑 收藏 引用 所属分类:
解题报告