C语言 枚举——熄灯问题

题目：

有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。
每个按钮的位置上有一 盏灯，当按下一个按钮后，该按钮以及周围位置(上边,下边,左边,右边)的灯都会改变状态。
（如果灯原来是点亮的，就会被熄灭。如果灯原来是熄灭的，则会被点亮）

分析：

●在矩阵角上的按钮改变3盏灯的状态
●在矩阵边上的按钮改变4盏灯的状态
●其他的按钮改变5盏灯的状态

●与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果

要求：

给定矩阵中每盏灯的初始状态，求一种按按钮方案，使得所有的灯都熄灭

输入：
● 第一行是一个正整数N，表示需要解决的案例数
● 每个案例由5行组成，每一行包括6个数字
● 这些数字以空格隔开，可以是0或1
● 0表示灯的初始状态是熄灭的
● 1表示灯的初始状态是点亮的

输出：
对每个案例，首先输出一行，输出字符串"PUZZLE #m"，其中m是该案例的序号
接着按照该案例的输入格式输出5行：
● 1表示需要把对应的按钮按下
● 0表示不需要按对应的按钮.
● 每个数字以一个空格隔开

解题思路：

1. 在第1行的各开关状态确定的情况下，这些开关作用过后，将导致第1行某些灯是亮的,某些灯是灭的。

2. 要熄灭第1行某个亮着的灯(假设位于第 i 列)，那么唯一的办法就是按下第2行第 i 例的开关。
   (因为第1行的开关已经用过了，而第3行及其后的开关不会影响到第1行)
   为了使第1行的灯全部熄灭，第2行的合理开关状态就是唯一的。

3. 同理，要想让第2行的灯熄灭，就要按下第3行的按钮，第3排的灯的状态唯一。

4. 以此类推，最后一行灯的状态是唯一的。 故，确定第一行的灯的状态，其余行就随之唯一确定

5. 枚举第1行的状态共2^6种。

代码：

#include<stdio.h>
#include<string.h> 
char oriLights[5];	
//初始5行灯的矩阵,一个字符占 1 byte = 8 bit，一行有6盏灯，6位二进制数即可。
char lights[5]; 	//变化中灯的矩阵
char result[5];		//灯的状态结果 

int GetBit(char c,int i) 	//取字符c的第i个比特
{
	return (c>>i)&1; 		//c右移i位，与1做与运算，1&1=1，1&0=0
} 
void SetBit(char &c,int i,int v)	//c的第i位改为v 
{
	if(v==1)
	{
		c|=(1<<i);	//1左移i位和c做或运算
	} 
	else
	{
		c&=~(1<<i);		//1左移i位后取反，在和c做与运算
	}
}
void FlipBit(char &c,int i)		//改变灯的状态
{
	c^=(1<<i); 	//异或，相同为0，不同为1
}
void OutputResult(int t,char result[])
//输出第t组案例的结果
{
	printf("PUZZLE #%d\n",t);
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<6;j++)
		{
			printf("%d ",GetBit(result[i],j));
			
		}
		printf("\n");
	}
	printf("\n");
} 

int main()
{
	int T;
	scanf("%d",&T);	 //输入需要检测的案例组数
	for(int t=1;t<=T;T++)
	//循环检测每一组
	{
		for(int i=0;i<5;i++)
		//每组5行		
		{
			for(int j=0;j<6;j++)
			//每行6个按钮
			{
				int s;
				scanf("%d",&s);		//输入0或1表示每个灯的状态
				SetBit(oriLights[i],j,s);	//将状态存入对应的oriLights[i]的第j位
			}
		}
		for(int n=0;n<64;n++)
		//枚举第1行按钮有2^6=64种按语不按的选择
		{
			int switchs = n;	//将第1行的状态赋给switch
			memcpy(lights,oriLights,sizeof(oriLights));
			//将初始状态oriLights赋值给lights，保证初始状态不被改变
			for(int i=0;i<5;i++)
			//枚举在第n状态下的每一行
			{
				result[i] = switchs;
				//将switch中的状态存入result[i]中，方便后面输出结果
				for(int j=0;j<6;j++)
				//对此行的每一个按钮进行处理
				{
					if(GetBit(switchs,j))	
					//如果状态为1，则按下按钮，左右以及自身状态发生变化
					{
						if(j>0)
							FlipBit(lights[i],j-1);
						FlipBit(lights[i],j);
						if(j<5)
							FlipBit(lights[i],j+1);
					}
				}
				if(i<4)
				//若是前四行，则此按钮的下方灯也改变状态
				{
					lights[i+1]^=switchs;
				}
				switchs = lights[i];
				//第i+1行的状态
			}
			if(lights[4]==0)	//若最后一行全熄灭，则输出
			{
				OutputResult(t,result);
				break;
			}
		}
	}
	return 0;
}

运行结果：