枚举2--熄灯问题

  1 /*
  2 分析：
  3     方法一：枚举所有可能
  4         总共5*6=30展灯，所有可能情况为2^30，所以肯定不行
  5     方法二：如果局部状态确定，那么其余状态也被确定，那么我们只用例举局部状态即可
  6         当第一行的灯光操作之后，我们可以操作第二行的灯光将第一行的灯光全部熄灭，而此时第二行的灯光也是唯一确定的。
  7         而第三，第四等行影响不到第一行。同理第二行的灯光确定后，第三行把第二行全部调熄，那么第三行也是唯一确定的。
  8         同理第四行，第五行也是唯一确定的。
  9         所以当确定第一行之后，所有的行都是唯一确定的，我们看这个所有灯的唯一确定的情况是否使所有的灯熄灭从而判断解是否为可行解。
 10         其实我们只要判断第五行即可，因为照之前的规则，前四行肯定是熄灯的。
 11         所以我们只用枚举第一行就可以枚举所有的情况。
 12         情况总数为：2^6，每种情况都要调所有的30盏灯，执行次数为2^6*5*6（下面的代码编程我们选这种）
 13         
 14         优化：
 15             若是把列看成行，情况总数为2^5，执行次数为2^5*6*5
 16             
 17             
 18         执行2^6的时候，我们可以用6层循环，我们也可以用数字的二进制来表示。我们选择用数字的二进制来表示。
 19         
 20         
 21     
 22 */
 23 
 24 
 25 #include <iostream>
 26 using namespace std;
 27 int puzzle[6][8],press[6][8];//这里用6行8列是保证按规定按钮影响的都是周围5盏灯的情况，注意，不是7行8列，因为最后一行不会被下一行影响
 28 
 29 bool guess(){//这个函数时对第一行每一个的选择情况进行判断
 30     int c,r;//r表示行，c表示列
 31     for(r=1;r<5;r++){
 32         for(c=1;c<7;c++){
 33             //下一行的按键是为了把上一行的按键整熄，作用每一个灯的有上下左右自己和自己的初始情况
 34             //下按=（自己初始状态+自己按+左按+右按+上按）
 35             press[r+1][c]=(puzzle[r][c]+press[r][c]+press[r][c-1]+press[r][c+1]+press[r-1][c])%2;
 36         }
 37     }
 38     for(c=1;c<7;c++){//判断最后一行是否全部熄灯
 39         //如果最后一行各个按钮对灯的作用与初始状态保存一致，则说明是熄灯的。
 40         //例如如果总的作用为1，表示按一下，如果之前初始状态也是1，那么原来亮着的灯就熄了
 41         //对一个灯按奇数次的效果和按一次的效果一样
 42         if((press[5][c-1]+press[5][c]+press[5][c+1]+press[4][c])%2!=puzzle[5][c])
 43             return (false);
 44     }
 45     return (true); 
 46 }
 47 
 48 void enumerate(){//这个函数枚举第一行所有的情况
 49     int c;
 50     bool success;
 51     for(c=1;c<7;c++){
 52         press[1][c]=0;//对按钮方阵初始化
 53     }
 54     /*
 55         press[1][1]:1   c:1   press[1][c]=press[1][1]>1不成立  1 0 0 0 0 0 表示的是第一盏灯开，其余5盏灯熄
 56         press[1][1]:2   c:1   press[1][c]=press[1][1]>1成立    press[1][c]=press[1][1]:0  c++:2  press[1][c]=press[1][2]:1
 57             press[1][c]=press[1][2]>1不成立  0 1 0 0 0 0 表示的是第二盏灯开，其余5盏灯熄 
 58         press[1][1]:3   c:1   press[1][c]=press[1][1]>1成立    press[1][c]=press[1][1]:0  c++:2  press[1][c]=press[1][2]:2
 59             press[1][c]=press[1][2]>1成立    press[1][c]=press[1][2]:0  c++:3  press[1][c]=press[1][3]:1  
 60             0 0 1 0 0 0 表示的是第三盏灯开，其余5盏灯熄 
 61         以此类推
 62         
 63     */
 64     while(guess()==false){
 65         press[1][1]++;
 66         c=1;
 67         while(press[1][c]>1){
 68             press[1][c]=0;
 69             c++;
 70             press[1][c]++;
 71         }
 72     }
 73     return;
 74 }
 75 
 76 int main(){
 77     freopen("2in.txt","r",stdin);
 78     int cases,i,r,c;
 79     
 80     //对周围按钮进行初始化
 81     for(r=0;r<6;r++)
 82         press[r][0]=press[r][7]=0;
 83     for(c=1;c<7;c++){
 84         press[0][c]=0;
 85     }
 86     //录入数据，灯泡的初始状态
 87     for(r=1;r<6;r++){
 88         for(c=1;c<7;c++){
 89             scanf("%d",&puzzle[r][c]);
 90         }
 91     }
 92 
 93     enumerate();//进行枚举判定
 94     printf("PUZZLE #1\n");
 95     //输出结果
 96     for(r=1;r<6;r++){
 97         for(c=1;c<7;c++){
 98             printf("%d ",press[r][c]);
 99         }
100         printf("\n");
101     }
102     return 0;
103 }