点灯游戏是一个十分有趣的智力游戏,他的规则是这样的:
有一行N行N列的灯,开始时全部是灭的, 当你点击其中一盏灯是他的上下左右(若存在的话)状态全部改变,现在要求你在限定的时间内以最少地步数,将全部的灯点亮.
昨天收到了个这封Ｅ－mail，回去想了想，今早编了下，出来是基本上出来了，但算法却太过复杂，时间耗费太长，我用的是穷举，大家一起帮忙想想，
我把我的程序附上来：
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#define MAX 10
typedef struct
{
unsigned int st:1;
unsigned int :7; /*构成一个字节*/
}light;
light matrix[MAX][MAX];
int num;
void initial(void);
void tackle(int i);
int main()
{
int test=0,counter=0,i,j;
short *help=NULL;
initial();
puts("Enter a number:");
scanf("%d",&num);
help=(short *)malloc(sizeof(short)*num*num);
for(i=0;i<num*num;i++)
help[i]=0;
while(1)
{
for(i=0;i<num*num;i++)
{
if(!help[i]) /*进行二进制编码 */
{
help[i]=1;
for(j=i-1;j>=0;j--)
help[j]=1-help[j];
break;
}
else test++;
}
if(test==num*num)
break;
else test=0;
for(i=0;i<num*num;i++)
if(help[i]==1)
tackle(i);
if(check())
initial();
else break;
}
for(i=0;i<num*num;i++)
if(help[i]==1)
printf("STEP%02d:(%d,%d)\n",counter++,i/num,i%num);
free (help);
getch();
return 0;
}
void initial(void) /*初始化或用于还原*/
{
int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
matrix[i][j].st=0;
}
void tackle(int i) /*函数用于处理该位置和它上下左右的变化*/
{
matrix[i/num][i%num].st=1-matrix[i/num][i%num].st;
if(i/num<num-1)
matrix[i/num+1][i%num].st=1-matrix[i/num+1][i%num].st;
if(i/num>0)
matrix[i/num-1][i%num].st=1-matrix[i/num-1][i%num].st;
if(i%num<num-1)
matrix[i/num][i%num+1].st=1-matrix[i/num][i%num+1].st;
if(i%num>0)
matrix[i/num][i%num-1].st=1-matrix[i/num][i%num-1].st;
}
int check(void) /*函数用于检查程序是否已经算出结果。*/
{
int i,j;
for(i=0;i<num;i++)
for(j=0;j<num;j++)
if(matrix[i][j].st==0)
return 1;
return 0;
}
下面的程序用于检验上面的结果：
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
typedef struct
{
unsigned int op:1;
unsigned int st:1;
unsigned int :6;
}BOOL;
int check(BOOL **,int);
int main()
{
int num,i,j,op1,op2;
BOOL **matrix=NULL;
puts("Enter a number:");
scanf("%d",&num);
matrix=(BOOL **)malloc(sizeof(BOOL)*num*num);
if(matrix==NULL)
exit(0);
for(i=0;i<num;i++)
for(j=0;j<num;j++)
matrix[i][j].op=matrix[i][j].st=0;
while(check(matrix,num))
{
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
printf("%3d",matrix[i][j].st);
printf("\n");
}
printf("\n");
scanf("%d%*c%d",&op1,&op2);
fflush(stdin);
matrix[op1][op2].st=1-matrix[op1][op2].st;
if(op2>0)
matrix[op1][op2-1].st=1-matrix[op1][op2-1].st;
if(op1<num-1)
matrix[op1+1][op2].st=1-matrix[op1+1][op2].st;
if(op1>0)
matrix[op1-1][op2].st=1-matrix[op1-1][op2].st;
if(op2<num-1)
matrix[op1][op2+1].st=1-matrix[op1][op2+1].st;
}
puts("You are excellent!\n");
free(matrix);
getch();
}
int check(BOOL **matrix,int num)
{
int i,j;
for(i=0;i<num;i++)
for(j=0;j<num;j++)
if(matrix[i][j].st==0)
return 1;
return 0;
}
上面的程序并没有把全部可能的结果都算出来，当然要算出来再比较，找出一个最少的步数还是比较简单的，程序问题的关键不在这，程序最大的问题是效率太低，算５＊５时大约需要１０秒，算６*６就得等好一会，至于更大的数那就只能望洋兴叹了，所以本题重在讨论算法，欢迎大家一起讨论，多给些意见。
----------------解决方案--------------------------------------------------------
即然是算法讨论，那就把核心算法标出哦，这样看着很累人的！
----------------解决方案--------------------------------------------------------
不好意思。
我原本以为说了穷举大家就知道了。
点灯游戏的规则第一楼已经讲了．下面把我的思路说下，
n*n的方格，每个方格的灯只有亮与灭两种可能，对应的就是被人点了奇数次和被人点了偶数次（包括没点）两种可能．
因此每盏灯都有被人点奇数次和被人点偶数次两种可能，总共就是2^（n*n）种可能，穷举所有可能的操作，直到找到能把所有的灯点亮的方阵坐标．
light.st是用来标记灯的亮和灭的状态，help是我申请n*n位的数组，每位都有1和0两种变化，分别代表被点奇数次和被点偶数次这两种可能。在每次产生help一个０１数列时，函数tackle用于把help数组中为１的相应的方阵的坐标的灯以及它周围灯的亮灭状态改变，在以check函数检查方阵中灯的亮灭情况，直到找到把所有的灯都点亮停止循环。
----------------解决方案--------------------------------------------------------