블로그는 귀차니즘 :: The Blocks Problem

문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37
의 견 : 명령어 파싱에 대한 연습을 하는 문제라고 생각합니다. 한 가지 언어 특성상 Pointer를 이용한 List 형식으로 코드를 작성할 때 구현에 있어 난이도가 조금 있을 것입니다. 그리하여 STL을 부분적으로 사용했었고
, 아마 지금 재작성 한다면 table을 비롯하여 모든 부분을 STL으로 작성할 것 같습니다.
소스
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. }

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 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

블로그는 귀차니즘

The Blocks Problem

"Algorithm" 분류의 다른 글

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

댓글을 달아 주세요

카테고리

최근에 올라온 글

최근에 달린 댓글

달력

링크

최근에 받은 트랙백

글 보관함

태그목록

« 2010/03 »
일	월	화	수	목	금	토
	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