题目链接：
题意：给你十个俄罗斯方块，问你能否拼成指定长宽的矩形，方块下落的顺序是严格确定的，后下落的方块不能落在先下落的方块之下。
分析：这个题的方法跟 完全一致。具体分析参见
每个俄罗斯方块都是由更小的小方格拼成的， 可以用一个一维数组来记录每一列已经摞上了多少个小方格。DFS遵循底部放满原则，如果可以恰好和已存在的方块实现无缝拼接才往上放，否则回溯。
细心一些，把情况考虑清楚即可。
1 #include2 #include 3 #include 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) //90105 {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 ) //180115 {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) //270123 {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 ) //0139 {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) //90149 {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 ) //0163 {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 ) //90173 {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 ) //0187 {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 ) //90198 {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 ) //180206 {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 ) //270217 {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 }