UVA 12113 Overlapping Squares，12113overlapping

UVA 12113 Overlapping Squares，12113overlapping

題意：

　　　總共有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;
}