关灯游戏求解算法含代码
标签:
•
文件类型: .rar
•
文件大小: 1.08MB
•
下载次数: 1
•
本程序为求解关灯游戏的算法,同时还有一个测试程序,
代码片段和文件信息
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
文件 49 2009-08-19 21:29 说明.txt
文件 3594 2009-08-02 10:11 AllOutAllOut.cpp
文件 4284 2009-07-31 12:32 AllOutAllOut.dsp
文件 520 2009-07-31 11:37 AllOutAllOut.dsw
文件 41984 2009-08-02 10:13 AllOutAllOut.ncb
文件 53760 2009-08-02 10:13 AllOutAllOut.opt
文件 1258 2009-08-02 10:11 AllOutAllOut.plg
文件 1527 2009-07-31 16:06 AllOutDebuga.obj
文件 0 2009-07-31 16:06 AllOutDebuga.sbr
文件 443392 2009-07-31 16:18 AllOutDebugAllOut.bsc
文件 557107 2009-08-02 10:11 AllOutDebugAllOut.exe
文件 800592 2009-08-02 10:11 AllOutDebugAllOut.ilk
文件 253625 2009-08-02 10:11 AllOutDebugAllOut.obj
文件 2001156 2009-08-02 10:09 AllOutDebugAllOut.pch
文件 1123328 2009-08-02 10:11 AllOutDebugAllOut.pdb
文件 0 2009-07-31 16:18 AllOutDebugAllOut.sbr
文件 91136 2009-08-02 10:11 AllOutDebugvc60.idb
文件 118784 2009-08-02 10:11 AllOutDebugvc60.pdb
文件 0 2009-07-31 18:41 AllOut关灯游戏.txt
文件 205746 2008-04-22 17:17 关灯游戏.swf
目录 0 2009-08-19 21:27 AllOutDebug
目录 0 2009-08-19 21:27 AllOut
----------- --------- ---------- ----- ----
5701842 22
/*
此程序为求关灯游戏的解的程序
经过测试关灯游戏的解不唯一.
*/
#include
using namespace std;
bool test(int* &rectfirstint* &rectsecondint &mint &nint* &wint &location)
{//回溯法的剪枝函数
int ij;
if(location==m*n-1)
for(i=0;i {
if(rectfirst[i]!=rectsecond[i])
return false;
}
else
{
j=location-n;
if(j<0)
return true;
else
return rectfirst[j]==rectsecond[j];
}
return true;
}
void add(int* &rectsecondint &mint &nint* &wint &locationint i)
{
location++;
if(i==0)
w[location]=0;
else
{
w[location]=1;
if(location-n>=0)
rectsecond[location-n]=1-rectsecond[location-n];
if(location%n>0)
rectsecond[location-1]=1-rectsecond[location-1];
rectsecond[location]=1-rectsecond[location];
if((location+1)%n>0)
rectsecond[location+1]=1-rectsecond[location+1];
if(location+n rectsecond[location+n]=1-rectsecond[location+n];
}
}
void resume(int* &rectsecondint mint nint* &wint &locationint i)
{
if(i==1)
{
if(location-n>=0)
rectsecond[location-n]=1-rectsecond[location-n];
if(location%n>0)
rectsecond[location-1]=1-rectsecond[location-1];
rectsecond[location]=1-rectsecond[location];
if((location+1)%n>0)
rectsecond[location+1]=1-rectsecond[location+1];
if(location+n rectsecond[location+n]=1-rectsecond[location+n];
}
location--;
}
bool search(int* &rectfirstint* &rectsecondint &mint &nint* &wint &location)
{//此函数中的add和resume的参数0 1 更改会影响找到的解(因为解不唯一)
if(location==m*n-1)
return true;
add(rectsecondmnwlocation0);
if(test(rectfirstrectsecondmnwlocation)==false||search(rectfirstrectsecondmnwlocation)==false)
{
resume(rectsecondmnwlocation0);
add(rectsecondmnwlocation1);
if(test(rectfirstrectsecondmnwlocation)==false||search(rectfirstrectsecondmnwlocation)==false)
{
resume(rectsecondmnwlocation1);
return false;
}
}
return true;
}
/*
bool search(int* &rectfirstint* &rectsecondint &mint &nint* &wint &location)
{//此函数中的add和resume的参数0 1 更改会影响找到的解(因为解不唯一)
if(location==m*n-1)
return true;
add(rectsecondmnwlocation1);
if(test(rectfirstrectsecondmnwlocation)==false||search(rectfirstrectsecondmnwlocation)==false)
{
resume(rectsecondmnwlocation1);
add(rectsecondmnwlocation0);
if(test(rectfirstrectsecondmnwlocation)==false||search(rectfirstrectsecondmnwlocation)==false)
{
resume(rectsecondmnwlocation0);
return false;
}
}
return true;
}
*/
int main()
{
int *rectfirst*rectsecondm=0n=0*wlocation=-1;
int ij;
//rect 存放二维数组m n为二维数组的行列w存放结果 location为w的有效数据个数
cout<<“此程序为求关灯游戏的一个可行解“< do
{
m=0;
n=0;
location=-1;
while(m<=0||n<=0)
{
cout<<“请输入行数和列数:“< cin>>m>>n;
}
rectfirst= new int[m*n];
rectsecond= new int[m*n];
w= new int[m*n];
cout<<“请输入灯的状态 1为亮 0为灭:“< for(i=0;i for(j=0;j
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
文件 49 2009-08-19 21:29 说明.txt
文件 3594 2009-08-02 10:11 AllOutAllOut.cpp
文件 4284 2009-07-31 12:32 AllOutAllOut.dsp
文件 520 2009-07-31 11:37 AllOutAllOut.dsw
文件 41984 2009-08-02 10:13 AllOutAllOut.ncb
文件 53760 2009-08-02 10:13 AllOutAllOut.opt
文件 1258 2009-08-02 10:11 AllOutAllOut.plg
文件 1527 2009-07-31 16:06 AllOutDebuga.obj
文件 0 2009-07-31 16:06 AllOutDebuga.sbr
文件 443392 2009-07-31 16:18 AllOutDebugAllOut.bsc
文件 557107 2009-08-02 10:11 AllOutDebugAllOut.exe
文件 800592 2009-08-02 10:11 AllOutDebugAllOut.ilk
文件 253625 2009-08-02 10:11 AllOutDebugAllOut.obj
文件 2001156 2009-08-02 10:09 AllOutDebugAllOut.pch
文件 1123328 2009-08-02 10:11 AllOutDebugAllOut.pdb
文件 0 2009-07-31 16:18 AllOutDebugAllOut.sbr
文件 91136 2009-08-02 10:11 AllOutDebugvc60.idb
文件 118784 2009-08-02 10:11 AllOutDebugvc60.pdb
文件 0 2009-07-31 18:41 AllOut关灯游戏.txt
文件 205746 2008-04-22 17:17 关灯游戏.swf
目录 0 2009-08-19 21:27 AllOutDebug
目录 0 2009-08-19 21:27 AllOut
----------- --------- ---------- ----- ----
5701842 22
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件举报,一经查实,本站将立刻删除。
评论列表(条)