点灯游戏
个十分有趣
智力游戏,他
规则是这样
:有
行N行N列
灯,开始时全部是灭
,当你点击其中
盏灯是他
上下左右(若存在
话)状态全部改变,现在要求你在限定
时间内以最少地步数,将全部
灯点亮. 现在,我们以某
盏灯为研究对象,显然,当此灯状态被改变奇数次后,灯被点亮.反的,被点击偶数次,灯则维持原来
熄灭状态不变.而促使灯状态改变
事件不外乎其上下左右(若存在
话)被点击.推而广的,只要所有
灯状态被改变奇数次,则可保证所有
灯全部被点亮.同时,应该,介绍说明
是,对每
盏灯来说,自身被点次奇数数和
次效果相同,这是
,对每盏灯来说,被点
次后,再点偶数次,自身他
上下左右(若存在
话)状态恢复原态.同样道理,自身被点偶数次,相当于没被点.故在最少步数
限制下,每盏灯要么没被点,要么仅被点
次. 我们很容易想到,可以用枚举
思路方法来解决问题,以4行4列为例,
如下:#
\"stdio.h\"#
\"
.h\"#
\"stdlib.h\"#
\"Conio.h\"
{ FILE *fp;
row=6;
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+1)>=0?a[i*4+j+1]:0; q=(i+1)>=0?a[(i+1)*4+j]:0; s=m+n+p+q+a[i*4+j];
(s%2
0)
; }}此算法
最大缺点是:循环次数太多,使N*N次,随着N次数地增加,执行时间加长. 为此又提出
种改进算法:我们知道对每
盏灯而言,每盏灯
状态改变次数仅和其上下左右(若存在
话)和自身被点次数有关.这样我们就可以对第
行利用枚举法.列出其所有
可能值,#
\"stdio.h\"#
\"
.h\"#
\"stdlib.h\"#
\"Conio.h\"
{ FILE *fp;
row=6;
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(k=0;k for(i=1;i for(j=0;j { s=a[(i-1)*row+j]; /* 上 */
(i-2>=0) s
a[(i-2)*row+j]; /*上上 */
(i-1>=0) {
(j-1>=0) s
a[(i-1)*row+j-1]; /*上左 */
(j+1 }
(s<=1) a[i*row+j]=1-s; /*self */
(s<=3) a[i*row+j]=3-s;
a[i*row+j]=1; } m=row-1; for(n=0;n { ss=a[m*row+n]+a[(m-1)*row+n]; /*上 self */
[Page]
(n-1>=0) ss
a[m*row+n-1]; /*左 */
(n+1
|
a[m*row+n+1]; /*右 */
(ss%2
0)
;
}
(n
row) { pr
f(\"\\n OK !\\n\"); fputs(\"\\n OK !\\n\",fp);
sum=0;
for(i=0;i
)
{ sum
a[i];
pr
f(\"-\",a[i]); fpr
f(fp,\"-\",a[i]);
((i+1)%n
0) pr
f(\"\\n\"),fputs(\"\\n\",fp);
} pr
f(\"点击次数:-.\\n\\n\", sum);
fpr
f(fp,\"点击次数:-.\\n\\n\", sum);
getch
;
}
} fclose(fp);
}
延伸阅读
最新评论