题意：
总共有6个2*2的正方形，判断是否能够成所给的形状。
思路：
一个正方形总共有9种摆放方式，对于整个地图来说摆放方式总共有2的9次方种摆放方式。然后将地图用9*5的数组表示，正方形的位置用其8个边的下标和4个中空的下标表示。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int bian[9][8]={
{1,3,9,13,18,19,21,22},
{3,5,11,15,20,21,23,24},
{5,7,13,17,22,23,25,26},
{10,12,18,22,27,28,30,31},
{12,14,20,24,29,30,32,33},
{14,16,22,26,31,32,34,35},
{19,21,27,31,36,37,39,40},
{21,23,29,33,38,39,41,42},
{23,25,31,35,40,41,43,44}};//2*2正方形的9种摆放方式的边坐标
int nei[9][4]={
10,11,12,20,
12,13,14,22,
14,15,16,24,
19,20,21,29,
21,22,23,31,
23,24,25,33,
28,29,30,38,
30,31,32,40,
32,33,34,42};//2*2正方形的9种摆放方式的中空坐标
char str[100];
int map[45],cot[10],map1[45];
int read()//读入数据
{
int h=0,cnt = 0, kk = 0;
for(int i=0;i<5;i++)
{
if(gets(str)==NULL)
return -1;
if(str[0]=='0')
return -1;
for(int j=0;j<9;j++)
{
map[kk++]=str[j] ==32?0:1;
if(str[j] != 32)
cnt++;
}
}
return cnt;
}
int count(int s)//计算总共使用了几个正方形
{
return s==0?0:count(s/2)+(s&1);
}
void stick(int p,int &cnt)//构建将第p个正方形贴上去后的地图
{
int i,j;
for(i=0;i<8;i++)
{
if(map1[bian[p][i]]==0)//第p个正方形边的位置如果没有边的话，边的数量+1
cnt++;
map1[bian[p][i]]=1;
}
for(i=0;i<4;i++)
{
if(map1[nei[p][i]]==1)//第p个正方形中空的位置如果有边的话，边的数量-1
cnt--;
map1[nei[p][i]]=0;
}
}
int main()
{
int flag,cnt;
int i,j,k;
int h=1;
while((flag=read())&&flag!=-1)
{
//cout<<flag<<endl;
int flag1=0;
for(i=0;i<(1<<9);i++)
{
int n=count(i);
if(n>6||8*n<flag)
continue;
k=0;
for(j=0;j<9;j++)
if((i>>j)&1)
cot[k++]=j;
//cout<<k<<endl;
do
{
//cout<<1<<endl;
memset(map1,0,sizeof(map1));
cnt=0;
//cout<<n<<endl;
for(j=0;j<n;j++)
{
int p=cot[j];//cout<<1<<endl;
stick(p,cnt);
}
if(cnt==flag)
{
int flag2=1;
for(int l=0;l<45;l++)
{
if(map[l]!=map1[l])
{
flag2=0;break;
}
}if(flag2)
flag1=1;
}
if(flag1)
break;
}
while(next_permutation(cot,cot+k));
}
printf("Case %d: %s\n",h++, flag1? "Yes" : "No");
}
return 0;
}