世界名画陈列馆问题的源代码

世界名画陈列馆由m×n个陈列室组成。为防止名画被窃，需在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在陈列室相邻的前、后、左、右4个陈列室。请设计一个安排警卫机器人哨位的方案，使得名画陈列馆中每一个陈列室都在警卫机器人监视之下，且所用的警卫机器人最少。 经典算法题目，有回溯法、分支限界法等......

#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[]）;//放置机器人
	void recover（int iint jint a[]）;
	void Backtrack（int iint j）;
	void GreedySearch（）;	//贪婪搜索
	int search（int iint j）;	//搜索在a[i][j]处设置机器人时它所监督未被监督的陈列室个数
	void set（int iint j）;		
	int mn;	//陈列馆的行数列数
	int mn;		//陈列室个数
	int g_num;	//陈列室中已被监视的个数
	int num;	//当前机器人个数
	int num1;	//用于贪心搜索中机器人的个数
	int **x;	//当前解
	int bestn;	//当前最优解的个数
	int **bestx;//当前最优解
};


void Exhibit_hall::set（int iint jint a[]）//x[][]为1表示此房间已放置了一个机器人，为2表示此房间已被监视
{
	num++;
	a[0]=x[i][j];
	if（a[0]==0） g_num++;//若此陈列室未被监视，则此时已被监视g_num++
	x[i][j]=1;//此位置放置了一个机器人
	if（x[i-1][j]==0） {a[1]=1;x[i-1][j]=2;g_num++;}//若上方未被监视则此时设置未已被监视
	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[]）//撤消机器人
{
	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;

	//当此陈列室已被监视，则没必要在此陈列室放设置警卫机器人
	//因为x[i+1][j+1]放置一机器人优于此处放机器人

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

	//在此陈列室被监视
	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）		//在此陈列室放置机器人
		{
			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

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件          3  2008-03-02 19:18  陈列馆问题\input.txt

     文件         43  2008-03-02 19:43  陈列馆问题\output.txt

     文件         40  2008-03-02 19:43  陈列馆问题\testout.txt

     文件       3437  2008-03-02 19:20  陈列馆问题\Exhi_hall.dsp

     文件      74752  2008-03-02 19:43  陈列馆问题\Debug\vc60.idb

     文件     118784  2008-03-02 19:43  陈列馆问题\Debug\vc60.pdb

     文件    2103920  2008-03-02 19:20  陈列馆问题\Debug\Exhi_hall.pch

     文件     573495  2008-03-02 19:43  陈列馆问题\Debug\Exhi_hall.exe

     文件    1139712  2008-03-02 19:43  陈列馆问题\Debug\Exhi_hall.pdb

     文件     360897  2008-03-02 19:43  陈列馆问题\Debug\Exhi_hall.obj

     文件     820444  2008-03-02 19:43  陈列馆问题\Debug\Exhi_hall.ilk

     文件      33792  2008-03-02 19:45  陈列馆问题\Exhi_hall.ncb

     文件        761  2008-03-02 19:43  陈列馆问题\Exhi_hall.plg

     文件        475  2008-03-02 19:28  陈列馆问题\readme.txt

     文件      48640  2008-03-02 19:45  陈列馆问题\Exhi_hall.opt

     文件        526  2008-03-02 19:45  陈列馆问题\Exhi_hall.dsw

     文件       4263  2008-03-03 20:30  陈列馆问题\Exhi_hall.cpp

     目录          0  2008-03-02 19:20  陈列馆问题\Debug

     目录          0  2007-12-21 20:15  陈列馆问题

----------- ---------  ---------- -----  ----

              5283984                    19