求一个算法实现

来源:百度知道 编辑:UC知道 时间:2024/05/31 04:08:12
有一个十分有趣的智力游戏,他的规则是这样的:有一行N行N列的灯,开始时全部是灭的,
当你点击其中一盏灯是他的上下左右(若存在的话)状态全部改变,现在要求你在限定的时间内以最少

地步数,将全部的灯点亮.

现在,我们以某一盏灯为研究对象,显然,当此灯状态被改变奇数次后,灯被点亮.反之,被点击偶数次,
灯则维持原来的熄灭状态不变.而促使灯状态改变的事件不外乎其上下左右(若存在的话)被点击.
推而广之,只要所有的灯状态被改变奇数次,则可保证所有的灯全部被点亮.同时,应该,说明的是,
对每一盏灯来说,自身被点次奇数数与一次效果相同,这是因为,对每盏灯来说,被点一次后,再点偶数次,
自身他的上下左右(若存在的话)状态恢复原态.同样道理,自身被点偶数次,相当于没被点.故在最少步数
的限制下,每盏灯要么没被点,要么仅被点一次.
我们很容易想到,可以用枚举的方法来解决问题,以4行4列为例, 程序如下:

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"conio.h"

main()
{ FILE *fp;
int row=6;
int a[100]={0},i,j,m,n,k,s,ss,sum;
clrscr();
for(a[0]=0;a[0]<=1;a[0]++)
for(a[1]=0;a[1]<=1;a[1]++)
for(a[2]=0;a[2]<=1;a[2]++)
for(a[3]=0;a[3]<=1;a[3]++)
for(a[4]=0;a[4]<=1;a[4]++)
for(a[5]=0;a[5]<=1;a[5]++)
.....
for(a[15]=0;a[15]<=1;a[15]++)
{ for(i=0;i<4;i++)
for(j=0;j<4;j++)
{ m=(i-1)>=0?a[(i-1)*4+j]:0;
n=(j-1)>=0?a[i*4+j-1]:0;
p=(j