#include
#include
using?namespace?std;

ifstream?fin?（“input.txt“）;
ofstream?fout（“output.txt“）;
ofstream?testout（“testout.txt“）;

class?Exhibit_hall{
	friend?void?Setrobot（int?int）;
	
private:
	void?set（int?iint?jint?a[]）;//放置機(jī)器人
	void?recover（int?iint?jint?a[]）;
	void?Backtrack（int?iint?j）;
	void?GreedySearch（）;	//貪婪搜索
	int?search（int?iint?j）;	//搜索在a[i][j]處設(shè)置機(jī)器人時(shí)它所監(jiān)督未被監(jiān)督的陳列室個(gè)數(shù)
	void?set（int?iint?j）;		
	int?mn;	//陳列館的行數(shù)列數(shù)
	int?mn;		//陳列室個(gè)數(shù)
	int?g_num;	//陳列室中已被監(jiān)視的個(gè)數(shù)
	int?num;	//當(dāng)前機(jī)器人個(gè)數(shù)
	int?num1;	//用于貪心搜索中機(jī)器人的個(gè)數(shù)
	int?**x;	//當(dāng)前解
	int?bestn;	//當(dāng)前最優(yōu)解的個(gè)數(shù)
	int?**bestx;//當(dāng)前最優(yōu)解
};


void?Exhibit_hall::set（int?iint?jint?a[]）//x[][]為1表示此房間已放置了一個(gè)機(jī)器人，為2表示此房間已被監(jiān)視
{
	num++;
	a[0]=x[i][j];
	if（a[0]==0）?g_num++;//若此陳列室未被監(jiān)視，則此時(shí)已被監(jiān)視g_num++
	x[i][j]=1;//此位置放置了一個(gè)機(jī)器人
	if（x[i-1][j]==0）?{a[1]=1;x[i-1][j]=2;g_num++;}//若上方未被監(jiān)視則此時(shí)設(shè)置未已被監(jiān)視
	if（x[i][j+1]==0）?{a[2]=1;x[i][j+1]=2;g_num++;}
	if（x[i+1][j]==0）?{a[3]=1;x[i+1][j]=2;g_num++;}
	if（x[i][j-1]==0）?{a[4]=1;x[i][j-1]=2;g_num++;}
}
	
void?Exhibit_hall::recover（int?iint?jint?a[]）//撤消機(jī)器人
{
	num--;
	x[i][j]=a[0];
	if（a[0]==0）?g_num--;

	if（a[1]）?{x[i-1][j]=0;g_num--;}
	if（a[2]）?{x[i][j+1]=0;g_num--;}
	if（a[3]）?{x[i+1][j]=0;g_num--;}
	if（a[4]）?{x[i][j-1]=0;g_num--;}
	a[0]=0;a[1]=0;a[2]=0;a[3]=0;a[4]=0;
}


void?Exhibit_hall::Backtrack（int?iint?j）//回溯
{
	if（i>m）{
		if（num		{
			for（int?k=1;k				for（int?l=1;l					bestx[k][l]=x[k][l];
			bestn=num;
		}
		return;
	}

	if（num+（mn-g_num）/5>=bestn）?return;

	//當(dāng)此陳列室已被監(jiān)視，則沒(méi)必要在此陳列室放設(shè)置警衛(wèi)機(jī)器人
	//因?yàn)閤[i+1][j+1]放置一機(jī)器人優(yōu)于此處放機(jī)器人

	if（x[i][j]!=0）
		Backtrack（i+j/nj%n+1）;

	//在此陳列室被監(jiān)視
	else
	{
		int?a[5]={0};
		if（i		{
			set（i+1ja）;
			Backtrack（ij）;
			recover（i+1ja）;
		}
		if（（j		{
			set（ij+1a）;
			Backtrack（ij）;
			recover（ij+1a）;
		}
		if（x[i+1][j]==0&&x[i][j+1]==0）		//在此陳列室放置機(jī)器人
		{
			set（ija）;
			Backtrack（ij）;
			recover（ija）;
		}
	}
}
int?Exhibit_hall::search（int?iint?j）
{
	if（i==m+1||j==n+1）?return?0;
	int?count=0;
	if（x[i][j]==0）count?++;
	if（x[i-1][j]==0）count?++;
	if（x[i][j+1]==0）count?++;
	if（x[i+1][j]==0）count?++;
	if（x[i][j-1]==0）count?++;
	return?count;
}
void?Exhibit_hall::set（int?iint?j）
{
	num1++;
	x[i][j]=1;

	if（x[i-1][j]==0）x[i-1][j]=2;
	if（x[i][j+1]==0）x[i][j+1]=2;
	if（x[i+1][j]==0）x[i+1][j]=2;
	if（x[i][j-1]==0）x[i][j-1]=2;
}
	
void?Exhibit_hall::GreedySearch（）
{
	for（int?i=1;i<=m;i++）
		for（int?j=1;j<=n;j++）
		{
			if（x[i][j]==0）
			{
				int?a1=0a2=0a3=0;
				a1=search（ij）;
				a2=search（i+1j）;
				a3=search（ij+1）;
				if（a1>=a2&&a1>=a3）set（ij）;
				else{
					if（a2>=a3）
					{
						if（a2>a3）set（i+1j）;
						else?
							if（x[i+1][j]!=0&&x[i][j+1]==0）set（ij+1）;
							else?set（i+1j）;
					}
					else?set（ij+1）;
				}
			}
		}
	for（i=1;i<=m;i++）
		for

?屬性????????????大小?????日期????時(shí)間???名稱(chēng)
-----------?---------??----------?-----??----

?????文件??????????3??2008-03-02?19:18??陳列館問(wèn)題\input.txt

?????文件?????????43??2008-03-02?19:43??陳列館問(wèn)題\output.txt

?????文件?????????40??2008-03-02?19:43??陳列館問(wèn)題\testout.txt

?????文件???????3437??2008-03-02?19:20??陳列館問(wèn)題\Exhi_hall.dsp

?????文件??????74752??2008-03-02?19:43??陳列館問(wèn)題\Debug\vc60.idb

?????文件?????118784??2008-03-02?19:43??陳列館問(wèn)題\Debug\vc60.pdb

?????文件????2103920??2008-03-02?19:20??陳列館問(wèn)題\Debug\Exhi_hall.pch

?????文件?????573495??2008-03-02?19:43??陳列館問(wèn)題\Debug\Exhi_hall.exe

?????文件????1139712??2008-03-02?19:43??陳列館問(wèn)題\Debug\Exhi_hall.pdb

?????文件?????360897??2008-03-02?19:43??陳列館問(wèn)題\Debug\Exhi_hall.obj

?????文件?????820444??2008-03-02?19:43??陳列館問(wèn)題\Debug\Exhi_hall.ilk

?????文件??????33792??2008-03-02?19:45??陳列館問(wèn)題\Exhi_hall.ncb

?????文件????????761??2008-03-02?19:43??陳列館問(wèn)題\Exhi_hall.plg

?????文件????????475??2008-03-02?19:28??陳列館問(wèn)題\readme.txt

?????文件??????48640??2008-03-02?19:45??陳列館問(wèn)題\Exhi_hall.opt

?????文件????????526??2008-03-02?19:45??陳列館問(wèn)題\Exhi_hall.dsw

?????文件???????4263??2008-03-03?20:30??陳列館問(wèn)題\Exhi_hall.cpp

?????目錄??????????0??2008-03-02?19:20??陳列館問(wèn)題\Debug

?????目錄??????????0??2007-12-21?20:15??陳列館問(wèn)題

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

??????????????5283984????????????????????19