poj 1753 filp game 2015年暑假训练第一题 枚举

题意就是说：翻牌，随便翻到一张牌，其上下左右随他都得翻，看最少用翻几张牌，能够让16张牌全为正或全为负。

这道题有一个大坑，就是每一张牌其实只能翻奇数次，比如翻的顺序为 （3，2）->   (2,2)  ->  (3,2)   = =   (2,2)  是  等价的

故最多翻的个数是16，从0到16一个一个测试，枚举的是翻牌的个数，若全为正或反，则断开枚举，否则一直枚举

最多有C（0，16）+C（1，16）+。。。+C（16，16）=2^16次，

这道题首先是用dfs码的，但是最麻烦的情况下会超时吧，比如Impossible;//不会改，我只是一名小牛

后来用枚举翻牌个数打的，期间遇到很多问题；

1：二维变一维，在翻牌时要注意关联牌的翻转；

2：一般组合代码的实现，即16个牌中抽n个牌的代码n>=0,n<=16;

3:  翻牌后若不为全，还得翻回来；//其实可以把实参数组传递给形参解决；

一般组合组合的代码如下：省略打的

int n,m;
cin>>n>>m;
int rcd[10];
int num[10];
void select_combination(int l,int p)
{
    int i;
    if(l==m)
    {
       for(i=0;i<m;i++) 
       {
           cout<<rcd[i];
           if(i<m-1)
            cout<<' ';
       }
       cout<<endl;
       return ;
    }
    for(i=p;i<n;i++)
    {
        rcd[l]=num[i];
        select_combination(int l+1,int i+1)
    }
}
int mian()
{
    select_combination(0,0);
    return 0;
}

下面是我打的代码：

    #include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    char a[5][5];//二维
    char own[30];//一维
    int add[6]= {0,4,-4,1,-1};//翻转区域
    //queue<int> s;
    int num[30];
    int point;//
    int k=0;
    int n=16;
    int find()//发现是否出现全为0或全为1
    {
        int i;
        int k1=1,k2=1;
        for(i=0; i<16; i++) //判断是否全为黑色
        {
            if(own[i]=='0')//有白色
            {
                k1=0;
            }
            if(own[i]=='1')//有黑色
            {
                k2=0;
            }
        }
        if(k1==0&&k2==0)//既有白，又有黑
        {
            return -1;
        }
        else
            return 0;//全
    }
    int tell(int i)//判断是否出界
    {
        if(i<0||i>=16)
            return 0;
        else
            return 1;
    }
    void fanzhuan(int k)//进行翻转
    {
        int p;
        int i;
        for(i=0; i<3; i++)
        {
            p=k+add[i];
            if(tell(p)==1)
            {
                if(own[p]=='1')
                    own[p]='0';
                else
                    own[p]='1';
            }
        }
        int x=k%4;
        if(x==0)
        {
          p=k+1;
            if(tell(p)==1)
            {
                if(own[p]=='1')
                    own[p]='0';
                else
                    own[p]='1';
            }
        }
        else if(x==3)
        {
             p=k-1;
             if(tell(p)==1)
            {
                if(own[p]=='1')
                    own[p]='0';
                else
                    own[p]='1';
            }
        }
        else
        {
           for(i=3;i<5;i++)
           {
               p=k+add[i];
               if(tell(p)==1)
               {
                if(own[p]=='1')
                    own[p]='0';
                else
                    own[p]='1';
               }
           }
 
        }
    }
    int panduan()
    {
        int i,j;
        for(i=0; i<point; i++)
        {
            int p=num[i];
            fanzhuan(num[i]);
        }
        if(find()==0)//全
            return 1;
        else
            return 0;
    }
    void  select_com(int l,int p)
    {
        int i;
        if(l==point)
        {
            int g=panduan();
            if(g==1)
            {
                k=1;
                cout<<point<<endl;
                return ;
            }
            else
            {
                int t=panduan();
            }
        }
        for(i=p; i<n; i++)
        {
            if(k==0)
            {
                num[l]=i;
                select_com(l+1,i+1);
            }
        }
    }
    int main()
    {
        while(cin>>a[0][0])
        {
            int i,j;
            int start=0;
            for(i=1; i<=3; i++)
            {
                cin>>a[0][i];
            }
            for(i=0; i<4; i++)
            {
                if(a[0][i]=='b')
                    a[0][i]='1';
                else
                    a[0][i]='0';
                own[start++]=a[0][i];
            }
            for(i=1; i<=3; i++)
            {
                for(j=0; j<4; j++)
                {
                    cin>>a[i][j];
                    if(a[i][j]=='b')//黑色
                        a[i][j]='1';
                    else//白色
                        a[i][j]='0';
                    own[start++]=a[i][j];//二维变一维
                }
            }
            int m=1;
            if(find()==0)
                cout<<0<<endl;
            else//枚举翻转个数m
            {
                while(m<16)
                {
                    point=m;
                    select_com(0,0);
                    if(k==1)
                        break;
                    m++;
                }
                if(k==0)
                    cout<<"Impossible"<<endl;
            }
            k=0;
        }
        return 0;
    }
 
 
 
 

测试案例如下：
代码已AC