HDU 3647 Tetris
44751 단어 HDU
제목: 러시아 사각형 10 개 를 드 리 겠 습 니 다. 길 고 넓 은 사각형 을 만 들 수 있 는 지 물 어보 세 요. 사각형 의 낙하 순 서 는 엄 격 히 확정 되 어 있 습 니 다. 나중에 떨 어 진 사각형 은 먼저 떨 어 진 사각형 아래 에 떨 어 질 수 없습니다.
분석: 이 문제 의 방법 은 POJ 1020 Anniversary Cake 과 완전히 일치한다.구체 적 분석 참조 http://blog.csdn.net/lyy289065406/article/details/6683250
모든 러시아 블록 은 더 작은 사각형 으로 만들어 져 있 으 며, 1 차원 배열 로 각 열 에 몇 개의 작은 사각형 이 쌓 여 있 는 지 기록 할 수 있다.DFS 는 바닥 을 가득 채 우 는 원칙 에 따라 존재 하 는 사각형 과 틈 이 없 는 연결 을 할 수 있다 면 위로 올 려 놓 고 그렇지 않 으 면 거 슬러 올라간다.
좀 세 심하게 상황 을 똑똑히 고려 하면 된다.
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4
5 char tet[20]; //
6 int box[45]; // ，
7 int m, n;
8
9 bool DFS( int cur )
10 {
11 if ( cur == 10 ) return true;
12
13 switch( tet[cur] )
14 {
15 case 'I' :
16 for ( int i = 0; i < n; i++ )
17 {
18 if ( box[i] + 4 <= m ) //
19 {
20 box[i] += 4;
21 if ( DFS( cur + 1 ) ) return true;
22 box[i] -= 4;
23 }
24 if ( i + 3 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i + 2] == box[i + 3] && box[i] + 1 <= m ) //
25 {
26 for ( int j = i; j < i + 4; j++ ) ++box[j];
27 if ( DFS( cur + 1 ) ) return true;
28 for ( int j = i; j < i + 4; j++ ) --box[j];
29 }
30 }
31 break;
32
33 case 'O':
34 for ( int i = 0; i < n; i++ )
35 {
36 if ( i + 1 < n && box[i] == box[i + 1] && box[i] + 2 <= m )
37 {
38 box[i] += 2;
39 box[i + 1] += 2;
40 if ( DFS( cur + 1 ) ) return true;
41 box[i] -= 2;
42 box[i + 1] -= 2;
43 }
44 }
45 break;
46
47 case 'L' :
48 for ( int i = 0; i < n; i++ )
49 {
50 if ( i + 1 < n && box[i] + 3 <= m && box[i] == box[i + 1] ) // L
51 {
52 box[i] += 3;
53 box[i + 1] += 1;
54 if ( DFS( cur + 1 ) ) return true;
55 box[i] -= 3;
56 box[i + 1] -= 1;
57 }
58
59 if (i + 2 < n && box[i] + 1 == box[i + 1] && box[i + 1] == box[i + 2] && box[i] + 2 <= m && box[i + 1] + 1 <= m ) // 90°
60 {
61 box[i] += 2;
62 box[i + 1] += 1;
63 box[i + 2] += 1;
64 if ( DFS( cur + 1 ) ) return true;
65 box[i] -= 2;
66 box[i + 1] -= 1;
67 box[i + 2] -= 1;
68 }
69
70 if (i + 1 < n && box[i] + 1 <= m && box[i + 1] + 3 <= m && box[i + 1] + 2 == box[i] ) // 180°
71 {
72 box[i] += 1;
73 box[i + 1] += 3;
74 if ( DFS( cur + 1 ) ) return true;
75 box[i] -= 1;
76 box[i + 1] -= 3;
77 }
78
79 if (i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i + 2] + 2 <= m ) // 270°
80 {
81 box[i] += 1;
82 box[i + 1] += 1;
83 box[i + 2] += 2;
84 if ( DFS(cur + 1) ) return true;
85 box[i] -= 1;
86 box[i + 1] -= 1;
87 box[i + 2] -= 2;
88 }
89
90 }
91 break;
92
93 case 'J' :
94 for ( int i = 0; i < n; i++ )
95 {
96 if (i + 1 < n && box[i] == box[i + 1] && box[i + 1] + 3 <= m ) //0
97 {
98 box[i] += 1;
99 box[i + 1] += 3;
100 if ( DFS(cur + 1) ) return true;
101 box[i] -= 1;
102 box[i + 1] -= 3;
103 }
104 if (i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i] + 2 <= m) //90
105 {
106 box[i] += 2;
107 box[i + 1] += 1;
108 box[i + 2] += 1;
109 if ( DFS( cur + 1 ) ) return true;
110 box[i] -= 2;
111 box[i + 1] -= 1;
112 box[i + 2] -= 1;
113 }
114 if (i + 1 < n && box[i] + 2 == box[i + 1] && box[i] + 3 <= m && box[i + 1] + 1 <= m ) //180
115 {
116 box[i] += 3;
117 box[i + 1] += 1;
118 if ( DFS( cur + 1 ) ) return true;
119 box[i] -= 3;
120 box[i + 1] -= 1;
121 }
122 if (i + 2 < n && box[i] == box[i + 1] && box[i + 2] + 1 == box[i + 1] && box[i] + 1 <= m && box[i + 2] + 2 <= m) //270
123 {
124 box[i] += 1;
125 box[i + 1] += 1;
126 box[i + 2] += 2;
127 if ( DFS(cur + 1) ) return true;
128 box[i] -= 1;
129 box[i + 1] -= 1;
130 box[i + 2] -= 2;
131 }
132 }
133 break;
134
135 case 'Z' :
136 for ( int i = 0; i < n; i++ )
137 {
138 if (i + 2 < n && box[i + 2] == box[i + 1] && box[i + 1] + 1 == box[i] && box[i] + 1 <= m && box[i + 1] + 2 <= m ) //0
139 {
140 box[i] += 1;
141 box[i + 1] += 2;
142 box[i + 2] += 1;
143 if ( DFS( cur + 1 ) ) return true;
144 box[i] -= 1;
145 box[i + 1] -= 2;
146 box[i + 2] -= 1;
147 }
148 if (i + 1 < n && box[i] + 1 == box[i + 1] && box[i] + 2 <= m && box[i + 1] + 2 <= m) //90
149 {
150 box[i] += 2;
151 box[i + 1] += 2;
152 if ( DFS( cur + 1 ) ) return true;
153 box[i] -= 2;
154 box[i + 1] -= 2;
155 }
156 }
157 break;
158
159 case 'S' :
160 for ( int i = 0; i < n; i++ )
161 {
162 if (i + 2 < n && box[i] == box[i + 1] && box[i + 1] + 1 == box[i + 2] && box[i + 1] + 2 <= m && box[i + 2] + 1 <= m ) //0
163 {
164 box[i] += 1;
165 box[i + 1] += 2;
166 box[i + 2] += 1;
167 if ( DFS(cur + 1) ) return true;
168 box[i] -= 1;
169 box[i + 1] -= 2;
170 box[i + 2] -= 1;
171 }
172 if (i + 1 < n && box[i + 1] + 1 == box[i] && box[i] + 2 <= m && box[i + 1] + 2 <= m ) //90
173 {
174 box[i] += 2;
175 box[i + 1] += 2;
176 if ( DFS(cur + 1) ) return true;
177 box[i] -= 2;
178 box[i + 1] -= 2;
179 }
180 }
181 break;
182
183 case 'T' :
184 for ( int i = 0; i < n; i++ )
185 {
186 if ( i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i + 1] + 2 <= m ) //0
187 {
188 box[i] += 1;
189 box[i + 1] += 2;
190 box[i + 2] += 1;
191 if ( DFS( cur + 1 ) ) return true;
192 box[i] -= 1;
193 box[i + 1] -= 2;
194 box[i + 2] -= 1;
195 }
196
197 if ( i + 1 < n && box[i] + 1 == box[i + 1] && box[i] + 3 <= m ) //90
198 {
199 box[i] += 3;
200 box[i + 1] += 1;
201 if ( DFS( cur + 1 ) ) return true;
202 box[i] -= 3;
203 box[i + 1] -= 1;
204 }
205 if ( i + 2 < n && box[i] == box[i + 2] && box[i + 1] + 1 == box[i] && box[i + 1] + 2 <= m ) //180
206 {
207 box[i] += 1;
208 box[i + 1] += 2;
209 box[i + 2] += 1;
210 if ( DFS( cur + 1 ) ) return true;
211 box[i] -= 1;
212 box[i + 1] -= 2;
213 box[i + 2] -= 1;
214 }
215
216 if ( i + 1 < n && box[i + 1] + 1 == box[i] && box[i + 1] + 3 <= m ) //270
217 {
218 box[i] += 1;
219 box[i + 1] += 3;
220 if ( DFS( cur + 1 ) ) return true;
221 box[i] -= 1;
222 box[i + 1] -= 3;
223 }
224 }
225 break;
226 }
227 return false;
228 }
229
230 int main()
231 {
232 while ( scanf( "%d%d", &n, &m ), n || m )
233 {
234 for ( int i = 0; i < 10; i++ )
235 {
236 getchar();
237 tet[i] = getchar();
238 }
239
240 memset( box, 0, sizeof(box) );
241
242 if ( DFS(0) ) puts("Yes");
243 else puts("No");
244 }
245 return 0;
246 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
