/*
此程序為求關燈游戲的解的程序
經過測試關燈游戲的解不唯一.
*/
#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??AllOut\AllOut.cpp

?????文件???????4284??2009-07-31?12:32??AllOut\AllOut.dsp

?????文件????????520??2009-07-31?11:37??AllOut\AllOut.dsw

?????文件??????41984??2009-08-02?10:13??AllOut\AllOut.ncb

?????文件??????53760??2009-08-02?10:13??AllOut\AllOut.opt

?????文件???????1258??2009-08-02?10:11??AllOut\AllOut.plg

?????文件???????1527??2009-07-31?16:06??AllOut\Debug\a.obj

?????文件??????????0??2009-07-31?16:06??AllOut\Debug\a.sbr

?????文件?????443392??2009-07-31?16:18??AllOut\Debug\AllOut.bsc

?????文件?????557107??2009-08-02?10:11??AllOut\Debug\AllOut.exe

?????文件?????800592??2009-08-02?10:11??AllOut\Debug\AllOut.ilk

?????文件?????253625??2009-08-02?10:11??AllOut\Debug\AllOut.obj

?????文件????2001156??2009-08-02?10:09??AllOut\Debug\AllOut.pch

?????文件????1123328??2009-08-02?10:11??AllOut\Debug\AllOut.pdb

?????文件??????????0??2009-07-31?16:18??AllOut\Debug\AllOut.sbr

?????文件??????91136??2009-08-02?10:11??AllOut\Debug\vc60.idb

?????文件?????118784??2009-08-02?10:11??AllOut\Debug\vc60.pdb

?????文件??????????0??2009-07-31?18:41??AllOut\關燈游戲.txt

?????文件?????205746??2008-04-22?17:17??關燈游戲.swf

?????目錄??????????0??2009-08-19?21:27??AllOut\Debug

?????目錄??????????0??2009-08-19?21:27??AllOut

-----------?---------??----------?-----??----

??????????????5701842????????????????????22