블로그는 귀차니즘

First Sensation
  • 공지
  • 지역로그
  • 태그
  • 방명록

The Blocks Problem

Algorithm 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>
    4.  
    5. using namespace std;
    6.  
    7. deque< int > *table;
    8. int *link;
    9. int BlockNum;
    10.  
    11. void returning( int index );
    12. void moving( int index1, int index2 );
    13. void piling( int index1, int index2 );
    14. void print();
    15.  
    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
    41.  
    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
    55.  
    56.                         returning( b );
    57.                         piling( a, b );
    58.  
    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. }
    72.  
    73. void returning( int index )
    74. {
    75.     int BlockIndex = link[ index ];
    76.     while( table[ BlockIndex ].back() != index ) {
    77.  
    78.         int Block = table[ BlockIndex ].back();
    79.         table[ Block ].push_back( Block );
    80.         table[ BlockIndex ].pop_back();
    81.         link[ Block ] = Block;
    82.     }
    83. }
    84.  
    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. }
    93.  
    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. }
    112.  
    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
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"Algorithm" 분류의 다른 글

Algorithm Traning Book - 다섯번째 문제 (0)2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)2008/06/09
3n+1 Problem (0)2008/02/17
Maximum Sum (0)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG ACM, ACM-ICPC, C++, ICPC, STL
받은 트랙백이 없고, 댓글이 없습니다.

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

댓글을 달아 주세요

◀ 이전페이지 1 ... 100 101 102 103 104 105 106 107 108 ... 110 다음페이지 ▶

블로그 이미지
First Sensation 귀차니스트
rss
  • 관리자
  • 글쓰기

카테고리

  • 전체 (110)
    • Computer (3)
    • Language (14)
    • Reverse Engineering (1)
    • Algorithm (9)
    • TopCoder (3)
    • Library (2)
    • Programming (19)
    • Programming Tip (9)
    • PSP-Programming (10)
    • Program (5)
    • Small Talk (31)
    • Document (4)

최근에 올라온 글

  • Gradient 작성중에 있습.... (3)
  • 게임&인터랙티브 애플리....
  • 한게임 자동테트리스 Ve.... (24)
  • Intel 64 And IA32 Arch.... (2)
  • 한게임 자동테트리스 Ve.... (24)

최근에 달린 댓글

  • 다운어덯게 받아요. difl 2008
  • 멋있네요 ㅎㅎ. 준호씨 2008
  • ^^; 그러셨군요.. 사실 동영.... 귀차니스트 2008
  • ㅋㅋ 속도 튜닝의 무서움 ㅜ.... 귀차니스트 2008
  • 관리자만 볼 수 있는 댓글입.... 비밀방문자 2008

달력

«   2009/01   »
일 월 화 수 목 금 토
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

링크

  • kkamagui 프로그래밍 세상.
  • 류광의 번역 이야기.
  • 서광열의 프로그래밍 언....
  • 준호씨의 블로그.
  • 최익필의 이름없는 블로그.
  • 위키는 귀차니즘.

최근에 받은 트랙백

  • 궁극의 예외처리. 이름없는 블로그 2008
  • Maximum sum. 티스토리 지점 2008

글 보관함

  • 2008/12 (1)
  • 2008/11 (4)
  • 2008/10 (2)
  • 2008/09 (3)
  • 2008/08 (5)

태그목록

  • Codegear
  • Gradient
  • Chaos
  • RCW
  • Codejock
  • HTML 파서
  • Xtream Toolkit Pro
  • boost::shared_ptr
  • TopCoder
  • Programming
  • 개발일지
  • 디코딩
  • Mouse Message
  • 보안
  • FreeType
  • Develope
  • 탑코더
  • Logitech
  • 부트로더
  • 테트리스
  • Parent
  • 버퍼 오버플로우
  • Secure
  • Graphi
  • LGT
  • Mine Sweeper
  • Inheritance
  • Shell
  • C
  • Catch

지역로그 : 태그 : 방명록 : 관리자 : 글쓰기
귀차니스트’s Blog is powered by Textcube 1.7.5 : Risoluto / Designed by DesignNia.net