题目描述：
一个规模为 W*H 的长方形 ， 其中 W*H＝40；
然后游戏依次随机生成10个块，这10个块为以下之一：
题目特别限制：不能使后面方块的某个格子在前面方块的下面。
求给定的这十个块能否拼成一个W*H的长方形。
题目分析：
首先规模不大，方块有10个，长方形面积为40，所以考虑深度优先搜索！
考虑到方块的旋转，比如 I 可以旋转变成 ---- ， 上述7种方块一共可以形成19种放置方式。
我们可以将这19种放置方式的位移向量用静态数组表示出来。
搜索顺序为依次从每一列选取未方格位置的最低点，在该位置放入给定方块，通过约束条件
进行剪枝，进入下一层深度搜索。
有一个比较简单的剪枝：若在放置方块P后，若在长方形中造成了空洞，则应该剪去。这很容
易判断，放置后，下方为空，则剪枝。
参考程序：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#define maxn 45
using namespace std ;
// state[i] 表示放置状态 I 的各种相对位移向量
// 里面的4组数据表示4个小块的位移
const int state[19][4][2] =
{
{{0,0},{0,1},{0,2},{0,3}}, //0
{{0,0},{1,0},{2,0},{3,0}}, //1
{{0,0},{0,1},{0,2},{1,0}}, //2
{{0,0},{1,0},{2,0},{2,1}}, //3
{{0,0},{0,1},{0,2},{-1,2}}, //4
{{0,0},{0,1},{1,1},{2,1}}, //5
{{0,0},{0,1},{0,2},{1,2}}, //6
{{0,0},{0,1},{1,0},{2,0}}, //7
{{0,0},{1,0},{1,1},{1,2}}, //8
{{0,0},{1,0},{2,0},{2,-1}}, //9
{{0,0},{0,1},{1,0},{1,1}}, //10
{{0,0},{0,1},{1,1},{1,2}}, //11
{{0,0},{0,1},{-1,1},{1,0}}, //12
{{0,0},{0,1},{0,2},{1,1}}, //13
{{0,0},{1,0},{2,0},{1,1}}, //14
{{0,0},{0,1},{0,2},{-1,1}}, //15
{{0,0},{0,1},{1,1},{-1,1}}, //16
{{0,0},{0,1},{-1,1},{-1,2}}, //17
{{0,0},{1,0},{1,1},{2,1}}, //18
} ;
const int idx[8] = {0,2,6,10,11,13,17,19}; // 索引数组
const char ch[] = "IJLOSTZ" ; // 字母映射成数字
int N , M , bd[maxn][maxn] , w[maxn];
inline bool IsOut(int x ,int y){ // 判断是否出界
return x<0||y<0||x>=M||y>=N ;
}
void put(int x,int y ,int u , int sig){ // 在(x,y)处放置方块u,标号sig
int i ,cx ,cy;
for(i = 0 ; i < 4 ; ++i ){
cx = x + state[u][i][0] ;
cy = y + state[u][i][1] ;
bd[cx][cy] = sig ;
}
}
bool check(int x,int y ,int u){ // 检查是否有空洞
int i , cx ,cy ;
for(i = 0 ; i<4 ; ++i){
cx = x + state[u][i][0] ;
cy = y + state[u][i][1] ;
if(!IsOut(cx-1,cy) && !bd[cx-1][cy]) return 0 ;
}
return 1 ;
}
bool DFS(int dep){
if(dep > 9) return 1 ;
int i , j , k , u ,t , cx , cy , chk;
for(j = 0 ; j < N ; ++j){
for(i = 0 ; i < M && bd[i][j] ; ++i) ; // 寻找j列中尚未放置的第一个格子
if(i == M) continue ;
for(k = idx[u=w[dep]] ; k < idx[u+1] ; ++k ){ // 对方块的各种旋转状态进行试探
chk = 0 ;
for(t=0 ; t<4 &&!chk; ++t ){
cx = i + state[k][t][0] ;
cy = j + state[k][t][1] ;
if((IsOut(cx,cy)||bd[cx][cy]) ) // 不满足约束
chk = 1 ;
}
if(chk == 1) continue ;
put(i,j,k,dep+1); // 放置
if(check(i,j,k) && DFS(dep+1)) return 1 ;
put(i,j,k,0); // 清理
}
}
return 0;
}
inline int findp(char chr){
int i ;
for(i = 0 ; i < 7 ; ++ i)
if(chr == ch[i]) return i ;
}
int main(){
int i , j;
char str[2] ;
while(scanf("%d%d",&N,&M)!=EOF && (N+M)){
for(i=0 ; i<10 ; ++i){
scanf("%s",str);
w[i] = findp(str[0]) ;
}
memset(bd , 0 ,sizeof(bd));
if( DFS(0) )
printf("Yes\n");
else
printf("No\n");
}
return 0 ;
}