当前位置: 代码迷 >> C语言 >> [讨论]点灯游戏的算法讨论
  详细解决方案

[讨论]点灯游戏的算法讨论

热度:862   发布时间:2006-07-20 13:34:34.0
[讨论]点灯游戏的算法讨论

点灯游戏是一个十分有趣的智力游戏,他的规则是这样的:
有一行N行N列的灯,开始时全部是灭的, 当你点击其中一盏灯是他的上下左右(若存在的话)状态全部改变,现在要求你在限定的时间内以最少地步数,将全部的灯点亮.
昨天收到了个这封E-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;
}

上面的程序并没有把全部可能的结果都算出来,当然要算出来再比较,找出一个最少的步数还是比较简单的,程序问题的关键不在这,程序最大的问题是效率太低,算5*5时大约需要10秒,算6*6就得等好一会,至于更大的数那就只能望洋兴叹了,所以本题重在讨论算法,欢迎大家一起讨论,多给些意见。

搜索更多相关的解决方案: 算法  游戏  点灯  

----------------解决方案--------------------------------------------------------
即然是算法讨论,那就把核心算法标出哦,这样看着很累人的!
----------------解决方案--------------------------------------------------------
不好意思。
我原本以为说了穷举大家就知道了。
点灯游戏的规则第一楼已经讲了.下面把我的思路说下,
n*n的方格,每个方格的灯只有亮与灭两种可能,对应的就是被人点了奇数次和被人点了偶数次(包括没点)两种可能.
因此每盏灯都有被人点奇数次和被人点偶数次两种可能,总共就是2^(n*n)种可能,穷举所有可能的操作,直到找到能把所有的灯点亮的方阵坐标.
light.st是用来标记灯的亮和灭的状态,help是我申请n*n位的数组,每位都有1和0两种变化,分别代表被点奇数次和被点偶数次这两种可能。在每次产生help一个01数列时,函数tackle用于把help数组中为1的相应的方阵的坐标的灯以及它周围灯的亮灭状态改变,在以check函数检查方阵中灯的亮灭情况,直到找到把所有的灯都点亮停止循环。
----------------解决方案--------------------------------------------------------
  相关解决方案