The Blocks Problem

Algorithm/Acm 2008/02/17 08:30 귀차니스트
  1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37
  2.  의   견   : 명령어 파싱에 대한 연습을 하는 문제라고 생각합니다. 한 가지 언어 특성상 Pointer를 이용한 List 형식으로 코드를 작성할 때 구현에 있어 난이도가 조금 있을 것입니다. 그리하여 STL을 부분적으로 사용했었고
    , 아마 지금 재작성 한다면 table을 비롯하여 모든 부분을 STL으로 작성할 것 같습니다.
  3. 소스
    101.cpp (Language : cpp)
    1. #include <iostream>
    2. #include <deque>
    3. #include <string>
    5. using namespace std;
    7. deque< int > *table;
    8. int *link;
    9. int BlockNum;
    11. void returning( int index );
    12. void moving( int index1, int index2 );
    13. void piling( int index1, int index2 );
    14. void print();
    16. int main( int argc, char **argv )
    17. {
    18.     cin >> BlockNum;
    19.     if( 0 < BlockNum && BlockNum < 25 ) {
    20.         table = new deque< int >[ BlockNum ];
    21.         link = new int[ BlockNum ];
    22.         for( int i = 0; i < BlockNum; i++ ) {
    23.             link[ i ] = i;
    24.             table[ i ].push_back( i );
    25.         }
    26.         string cmd1;
    27.         int a;
    28.         string cmd2;
    29.         int b;
    30.         while( true ) {
    31.             cin >> cmd1;
    32.             if( cmd1 == "quit" ) {
    33.                 print();
    34.                 break;
    35.             }
    36.             cin >> a >> cmd2 >> b;
    37.             if( a != b && link[ a ] != link[ b ] && 0 <= a && a < BlockNum && 0 <= b && b < BlockNum ) {
    38.                 if( cmd1 == "move" ) {
    39.                     if( cmd2 == "onto" ) {
    40.                         // move A onto B
    42.                         returning( a );
    43.                         returning( b );
    44.                         moving( a, b );
    45.                     }
    46.                     else if( cmd2 == "over" ) {
    47.                         // move A over B
    48.                         returning( a );
    49.                         moving( a, b );
    50.                     }
    51.                 }
    52.                 else if( cmd1 == "pile" ) {
    53.                     if( cmd2 == "onto" ) {
    54.                         // pile A onto B
    56.                         returning( b );
    57.                         piling( a, b );
    59.                     }
    60.                     else if( cmd2 == "over" ) {
    61.                         // pile A over B
    62.                         piling( a, b );
    63.                     }
    64.                 }
    65.             }
    66.         }
    67.         delete [] table;
    68.         delete [] link;
    69.     }
    70.     return 0;
    71. }
    73. void returning( int index )
    74. {
    75.     int BlockIndex = link[ index ];
    76.     while( table[ BlockIndex ].back() != index ) {
    78.         int Block = table[ BlockIndex ].back();
    79.         table[ Block ].push_back( Block );
    80.         table[ BlockIndex ].pop_back();
    81.         link[ Block ] = Block;
    82.     }
    83. }
    85. void moving( int index1, int index2 )
    86. {
    87.     int a = link[ index1 ];
    88.     int b = link[ index2 ];
    89.     table[ b ].push_back( table[ a ].back() );
    90.     table[ a ].pop_back();
    91.     link[ index1 ] = link[ index2 ];
    92. }
    94. void piling( int index1, int index2 )
    95. {
    96.     deque< int > temp;
    97.     int BlockIndex1 = link[ index1 ];
    98.     while( table[ BlockIndex1 ].back() != index1 ) {
    99.         temp.push_back( table[ BlockIndex1 ].back() );
    100.         table[ BlockIndex1 ].pop_back();
    101.     }
    102.     temp.push_back( table[ BlockIndex1 ].back() );
    103.     table[ BlockIndex1 ].pop_back();
    104.     int BlockIndex2 = link[ index2 ];
    105.     while( !temp.empty() ) {
    106.         int linkTemp = temp.back();
    107.         temp.pop_back();
    108.         table[ BlockIndex2 ].push_back( linkTemp );
    109.         link[ linkTemp ] = link[ index2 ];
    110.     }
    111. }
    113. void print()
    114. {
    115.     deque< int >::iterator prt;
    116.     for( int i = 0; i < BlockNum; i++ ) {
    117.         cout << i << ":";
    118.         prt = table[ i ].begin();
    119.         while( prt != table[ i ].end() ) {
    120.             cout << " " << *prt;
    121.             prt++;
    122.         }
    123.         cout << endl;
    124.     }
    125. }
크리에이티브 커먼즈 라이센스
Creative Commons License

"Algorithm / Acm" 분류의 다른 글

LCD Display (3)2008/02/17
Maximum Sum (0)2008/02/17
The Skyline Problem (2)2008/02/17
Ecological Bin Packing (0)2008/02/17
3n+1 Problem (0)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG , , , ,
받은 트랙백이 없고, 댓글이 없습니다.

트랙백 주소 :: http://www.filewiki.net/tc/trackback/5

댓글을 달아 주세요

◀ 이전페이지 1 ... 113 114 115 116 117 118 119 120 121 ... 123 다음페이지 ▶