题意：给你十个俄罗斯方块，问你能否拼成指定长宽的矩形，方块下落的顺序是严格确定的，后下落的方块不能落在先下落的方块之下。
每个俄罗斯方块都是由更小的小方格拼成的， 可以用一个一维数组来记录每一列已经摞上了多少个小方格。DFS遵循底部放满原则，如果可以恰好和已存在的方块实现无缝拼接才往上放，否则回溯。
#include#include using namespace std;char tet[20]; //记录方块的下降次序int box[45]; //把方块分成小格子，记录每列有多个小格子int m, n;bool DFS( int cur ){ if ( cur == 10 ) return true; switch( tet[cur] ) { case 'I' : for ( int i = 0; i < n; i++ ) { if ( box[i] + 4 <= m ) //判断能不能竖着放 { box[i] += 4; if ( DFS( cur + 1 ) ) return true; box[i] -= 4; } 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 ) //能不能横着放 { for ( int j = i; j < i + 4; j++ ) ++box[j]; if ( DFS( cur + 1 ) ) return true; for ( int j = i; j < i + 4; j++ ) --box[j]; } } break; case 'O': for ( int i = 0; i < n; i++ ) { if ( i + 1 < n && box[i] == box[i + 1] && box[i] + 2 <= m ) { box[i] += 2; box[i + 1] += 2; if ( DFS( cur + 1 ) ) return true; box[i] -= 2; box[i + 1] -= 2; } } break; case 'L' : for ( int i = 0; i < n; i++ ) { if ( i + 1 < n && box[i] + 3 <= m && box[i] == box[i + 1] ) //正着放L { box[i] += 3; box[i + 1] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 3; box[i + 1] -= 1; } 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° { box[i] += 2; box[i + 1] += 1; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 2; box[i + 1] -= 1; box[i + 2] -= 1; } if (i + 1 < n && box[i] + 1 <= m && box[i + 1] + 3 <= m && box[i + 1] + 2 == box[i] ) //顺时针旋转180° { box[i] += 1; box[i + 1] += 3; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 3; } if (i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i + 2] + 2 <= m ) //顺时针旋转270° { box[i] += 1; box[i + 1] += 1; box[i + 2] += 2; if ( DFS(cur + 1) ) return true; box[i] -= 1; box[i + 1] -= 1; box[i + 2] -= 2; } } break; case 'J' : for ( int i = 0; i < n; i++ ) { if (i + 1 < n && box[i] == box[i + 1] && box[i + 1] + 3 <= m ) //0 { box[i] += 1; box[i + 1] += 3; if ( DFS(cur + 1) ) return true; box[i] -= 1; box[i + 1] -= 3; } if (i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i] + 2 <= m) //90 { box[i] += 2; box[i + 1] += 1; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 2; box[i + 1] -= 1; box[i + 2] -= 1; } if (i + 1 < n && box[i] + 2 == box[i + 1] && box[i] + 3 <= m && box[i + 1] + 1 <= m ) //180 { box[i] += 3; box[i + 1] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 3; box[i + 1] -= 1; } 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 { box[i] += 1; box[i + 1] += 1; box[i + 2] += 2; if ( DFS(cur + 1) ) return true; box[i] -= 1; box[i + 1] -= 1; box[i + 2] -= 2; } } break; case 'Z' : for ( int i = 0; i < n; i++ ) { 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 { box[i] += 1; box[i + 1] += 2; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 2; box[i + 2] -= 1; } if (i + 1 < n && box[i] + 1 == box[i + 1] && box[i] + 2 <= m && box[i + 1] + 2 <= m) //90 { box[i] += 2; box[i + 1] += 2; if ( DFS( cur + 1 ) ) return true; box[i] -= 2; box[i + 1] -= 2; } } break; case 'S' : for ( int i = 0; i < n; i++ ) { 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 { box[i] += 1; box[i + 1] += 2; box[i + 2] += 1; if ( DFS(cur + 1) ) return true; box[i] -= 1; box[i + 1] -= 2; box[i + 2] -= 1; } if (i + 1 < n && box[i + 1] + 1 == box[i] && box[i] + 2 <= m && box[i + 1] + 2 <= m ) //90 { box[i] += 2; box[i + 1] += 2; if ( DFS(cur + 1) ) return true; box[i] -= 2; box[i + 1] -= 2; } } break; case 'T' : for ( int i = 0; i < n; i++ ) { if ( i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i + 1] + 2 <= m ) //0 { box[i] += 1; box[i + 1] += 2; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 2; box[i + 2] -= 1; } if ( i + 1 < n && box[i] + 1 == box[i + 1] && box[i] + 3 <= m ) //90 { box[i] += 3; box[i + 1] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 3; box[i + 1] -= 1; } if ( i + 2 < n && box[i] == box[i + 2] && box[i + 1] + 1 == box[i] && box[i + 1] + 2 <= m ) //180 { box[i] += 1; box[i + 1] += 2; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 2; box[i + 2] -= 1; } if ( i + 1 < n && box[i + 1] + 1 == box[i] && box[i + 1] + 3 <= m ) //270 { box[i] += 1; box[i + 1] += 3; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 3; } } break; } return false;}int main(){ while(cin>>n>>m&&n||m) { for(int i=0; i<10; i++) cin>>tet[i]; memset(box, 0, sizeof(box)); if(DFS(0)) cout<<"Yes"<
版权声明：本文为博主原创文章，未经博主允许不得转载。