http://acm.pku.edu.cn/JudgeOnline/problem?id=1108
Код:
#include <string> #include <cctype> #include <vector> #include <iostream> using namespace std; ////////////////////////// CLASS WINDOW ///////////////////////////// class Window { public: Window() {} Window( char A ); void disp(); void stretchX( int x ); void stretchY( int y ); void mergeX( Window win ); void mergeY( Window win ); vector<string> grid; int X, Y; }; Window :: Window( char A ) { grid.resize(3); grid[0] += A; grid[0] += "-*"; grid[1] = "| |"; grid[2] = "*-*"; X = Y = 2; } void Window :: disp() { for( int i = 0; i < grid.size(); i++ ) cout << grid[i] << endl; } void Window :: stretchX( int x ) { vector<int> pos(0), val(0); for( int i = 0; i <= X ; i++ ) { bool part = 0; for( int k = 0; k <= Y; k++ ) { if( grid[k][i] != ' ' && grid[k][i] != '-' ) { part = 1; break; } } if( part ) pos.push_back( i ); } int tot = 0; for( int i = 1; i < pos.size(); i++ ) { val.push_back( pos[i] - pos[i - 1] ); tot += val.back(); } pos.pop_back(); int j = x - X; while( pos.size() ) { for( int i = 0; i < val.back() * j / tot; i++ ) { for( int k = 0; k <= Y; k++ ) { if( isupper( grid[k][pos.back()] ) || grid[k][pos.back()] == '-' ) grid[k].insert( pos.back() + 1, "-" ); else if( grid[k][pos.back()] == '*' && grid[k][pos.back() + 1] != ' ' ) grid[k].insert( pos.back() + 1, "-" ); else grid[k].insert( pos.back() + 1, " " );; } } j -= val.back() * j / tot; tot -= val.back(); val.pop_back(); pos.pop_back(); } X = x; } void Window :: stretchY( int y ) { vector<int> pos(0), val(0); for( int i = 0; i <= Y ; i++ ) { bool part = 0; for( int k = 0; k <= X; k++ ) { if( grid[i][k] != ' ' && grid[i][k] != '|' ) { part = 1; break; } } if( part ) pos.push_back( i ); } int tot = 0; for( int i = 1; i < pos.size(); i++ ) { val.push_back( pos[i] - pos[i - 1] ); tot += val.back(); } pos.pop_back(); int j = y - Y; while( pos.size() ) { for( int i = 0; i < val.back() * j / tot; i++ ) { string temp = grid[pos.back()]; for( int k = 0; k <= X; k++ ) { if( isupper( temp[k] ) || temp[k] == '|' ) temp[k] = '|'; else if( temp[k] == '*' && grid[pos.back() + 1][k] != ' ' ) temp[k] = '|'; else temp[k] = ' '; } grid.insert( grid.begin() + pos.back() + 1, temp ); } j -= val.back() * j / tot; tot -= val.back(); val.pop_back(); pos.pop_back(); } Y = y; } void Window :: mergeX( Window win ) { for( int i = 0; i <= Y; i++ ) { if( isupper( win.grid[i][0] ) ) grid[i][X] = win.grid[i][0]; win.grid[i].erase( 0, 1 ); grid[i] += win.grid[i]; } X = grid[0].size() - 1; } void Window :: mergeY( Window win ) { for( int i = 0; i <= X; i++ ) if( isupper( win.grid[0][i] ) ) grid[Y][i] = win.grid[0][i]; for( int i = 1; i <= win.Y; i++ ) grid.push_back( win.grid[i] ); Y = grid.size() - 1; } ////////////////////////// CLASS TREE ///////////////////////////// class Tree { public: void input(); void disp(); void simplify(); string preorder; Window subgrid[26]; }; void Tree :: input() { cin >> preorder; for( int i = 0; i < preorder.size(); i++ ) if( isupper( preorder[i] ) ) subgrid[preorder[i] - 'A'] = Window( preorder[i] ); } void Tree :: disp() { subgrid[preorder[0] - 'A'].disp(); } void Tree :: simplify() { while( preorder.size() > 1 ) for( int i = 0; i < preorder.size() - 2; i++ ) { if( !isupper( preorder[i] ) && isupper( preorder[i + 1] ) && isupper( preorder[i + 2] ) ) { Window &winA = subgrid[preorder[i + 1] - 'A']; Window &winB = subgrid[preorder[i + 2] - 'A']; if( preorder[i] == '-' ) { if( winA.X > winB.X ) winB.stretchX( winA.X ); else if( winA.X < winB.X ) winA.stretchX( winB.X ); winA.mergeY( winB ); } else if( preorder[i] == '|' ) { if( winA.Y > winB.Y ) winB.stretchY( winA.Y ); else if( winA.Y < winB.Y ) winA.stretchY( winB.Y ); winA.mergeX( winB ); } preorder[i] = preorder[i + 1]; preorder.erase( i + 1, 2 ); if( preorder.size() == 1 ) break; } } } ////////////////////////// MAIN PROCCEDURE ////////////////////////// int main() { Tree T; int N; cin >> N; for( int i = 0; i < N; i++ ) { T.input(); T.simplify(); cout << i + 1 << endl; T.disp(); } }