枚举之一

//每一个点（i,j）最多做一次翻转,因为翻转两次相当于没有翻转//所以结果可以转化为一个只包含0、1的十六位数组，（1表示翻转）//枚举所有的可能性组合，逐个检验，取包含1最少的串 for(i=1;i<(1<<16);++i)#include<iostream>            //poj 2965  枚举，时间 922MS 险过    using namespace std;int table[4][4],tmp[4][4],i,j,k;char ch[4][5];int main(){    int c,num,inf=20,p[16],res[16];    for(i=0;i<4;++i)        scanf("%s",ch[i]);    for(i=0;i<4;++i)        for(j=0;j<4;++j)            if(ch[i][j]=='-')                table[i][j]=1;        //table[i][j]=1 表示open,0 表示closed    for(i=1;i<(1<<16);++i)    {        j=i;        c=0;num=0;        while(j)        {            p[c++]=j%2;            num+=j%2;            j/=2;        }        if(num>=inf)    //剪枝，如果某一数字所包含1的个数(即翻转次数)大于inf则不必讨论下去            continue;        for(j=0;j<4;++j)            for(k=0;k<4;++k)                tmp[j][k]=table[j][k];     //复制table到tmp        for(j=0;j<c;++j)        {            if(p[j]==0)                continue;            int a=j/4,b=j%4;    //j 转换成(x,y)二维坐标            for(k=0;k<4;++k)            {                    tmp[k][b]=(tmp[k][b]+1)%2;    //changes states of all handles in row i and all handles in column j.                tmp[a][k]=(tmp[a][k]+1)%2;            }            tmp[a][b]=(tmp[a][b]+1)%2;            }        int tag=1;        for(j=0;j<4&&tag;++j)            for(k=0;k<4&&tag;++k)                if(tmp[j][k]==0)    //如果有一个点是closed,则当然不是解决方案                    tag=0;        if(tag)        {            inf=num;    //前面已经保证 num<inf            for(j=0;j<16;++j)                res[j]=p[j];        }    }    printf("%d\n",inf);    for(i=0;i<16;++i)        if(res[i]==1)        {            printf("%d %d\n",i/4+1,i%4+1);        }    return 0;}

原文链接: https://www.cnblogs.com/mjc467621163/archive/2011/08/23/2150992.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍