POJ1222熄灯问题

问题描述：

程序代码：

/* *思路1：枚举所有可能的开关状态，对每个状态计算下最后灯的情况，看是否都熄灭 * 每种按钮有两种状态，一共有30个开关，那么状态数是2的30次方，太多不可取 *思路2：如何减少枚举的数目呢？        如果存在某个局部，一旦这个局部状态被确定后，那么剩余其他部分的状态只能        是确定的一种或者不多的n种，那么只需要枚举这个局部状态即可 */#include <memory>#include <string>#include <cstring>#include <iostream>using namespace std;/* *因为开关的状态只有0和1，并且每一行有六位，所以可以用一个char类型的字符来表示每一行的状态 *所以所有的状态可以用一个一维的字符数组来表示，通过对字符进行位运算来操作 */char oriLights[5];//存储初始灯的状态char lights[5];//存储变化中灯的状态char result[5];//存储灯的结果状态int GetBit(char c,int i)//获取字符c的第i位{    return (c>>i)&1;}void SetBit(char & c,int i,int v)//把字符c的第i为设置为v{    if(v)    {        c =c | (1<<i);//如果v为1，则把1左移i位，然后与c进行或运算    }    else        c =c & ~(1<<i);//如果v为0，则把把1左移i位取反，与c进行与运算}void FlipBit(char &c,int i){    c ^=(1<<i);//一个数和1异或就会被反转，和0异或不变}void OutputResult(int t,char result[]){    cout << "PUZZLE #" <<t<<endl;    for(int i=0;i<5;i++)    {        for( int j=0;j<6 ;j++)        {            cout<<GetBit(result[i],j);            if(j<5)                cout<< " ";        }        cout<<endl;    }}int main(){    int T;//有T组测试数据    cin>>T;    for(int t=1 ;t<=T; ++t)    {        for(int i=0;i<5;++i)            for(int j = 0;j<6 ;++j)            {                int s;//s代表数据第i行第j列的数据，0或1                cin>>s;                SetBit(oriLights[i],j,s);            }        //开始枚举第一行的所有状态        for(int n = 0; n<64;++n)        {            int switchs = n;//switchs 表示每一次循环第一行的状态            memcpy(lights,oriLights,sizeof(oriLights));//第一行的状体变化一次，就把初始状态赋给lights            for(int i=0; i< 5 ; ++i)            {//开始枚举在第一行已经确定的一种状态下，枚举所有行的状态                result[i] = switchs;//把第一行的状态保存到结果状态中                for(int j = 0;j< 6 ;++j)                {//枚举每一行的每一列的状态                    if(GetBit(switchs,j))//如果第i行第j列为1的话，表示灯亮,进行反转                    {                        if(j>0)                            FlipBit(lights[i],j-1);                        FlipBit(lights[i],j);                        if(j<5)                            FlipBit(lights[i],j+1);                    }                }                if( i < 5)//开始处理i+1行的灯                {                    lights[i+1] ^= switchs;//异或运算                }                switchs = lights[i];//把下一行的状态赋给switchs            }            if(lights[4]==0)            {                OutputResult(t,result);                break;            }        }    }    return 0;}结果已经在POJ上面运行通过