bowuguan.cpp

对大型活动的安排

/*
/*void robotout();//机器人占据房间//void robotin();//回溯，机器人离开房间*/
/*1是机器人占据的房间，1，2，3，4，5是房间可以占据的位置
   _
 _|2|_
|3 1 5|
~ |4|~
   ~
   机器人占据房间的方式，交点处为机器人的位置
   1        2     3      4       5       6       7         8        9      
   _|      |~    ~|     |_      -|      _|_      |-       ~|~       +
 (0,0)   (0,0) (0,0)   (0,0)   (0,0)   (0,0)   (0,0)    (0,0)      (0,0)
 (0,-1)  (0,1) (0,-1)  (0,1)   (0,-1)  (0,-1)  (0,1)    (0,-1)     (0,-1)
 (-1,0)  (1,0) (1,0)   (1,0)   (-1,0)  (0,1)   (-1,0)   (0,1)      (0,1)
                               (1,0)   (-1,0)  (1,0)    (1,0)      (-1,0)
							                                       (1,0)
*/
#include <iostream.h>

#define Max 30//定义一排最大的房间数
typedef struct RobotStatus{
	int x;
	int y;
	int roomx[4];
    int roomy[4];
	int total;
}robot;
class Robot{
public:
	int m,n;//纪录房间规模
	int room2r[Max][Max][3];//房间状态和它属于哪一个机器人
    int cannot[Max][Max][5];//纪录房间可以存在的位置,0-->可以走，1-->试探过,-1-->本来就不可以走
    robot r[300];//纪录Robot先后次序的数组
	int lastr;//纪录robot的个数
	//int rmod[9][4][2];//纪录机器人占有房间的形状，1~9;
    int roommod[5][2];//纪录机器人和房间的关系
	int r2dealx,r2dealy;
public:
	Robot(int M,int N);//初始化数组
	int next2deal();
	void initcannot();
	void initroommod();
	void initroom();
	void forward();
	void print();
	int testcannot(int x,int y);
	 backward();
	int go();//若能解出一组解，返回1，否则返回0
	void is_ok();//纪录房间若采用某种状态会不会矛盾
	



};
Robot::Robot(int M,int N)
{
	int i,j;
	m=M;n=N;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
				room2r[i][j][0]=0;
	lastr=0;
	//setrmod();
    initroommod();
	initroom();
	initcannot();
}
int Robot::next2deal()
{
	int i,j;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			if(room2r[i][j][0]==0)
			{
				r2dealx=i;
				r2dealy=j;
				//cout<<"\n\n\n\n"<<i<<" , "<<j<<endl;
				return 1;
			}
	return 0;//没有需要处理的房间了
}
int Robot::testcannot(int x,int y)
{
	int i,j;
	int test_x,test_y;//test_x，test_y为假设机器人的坐标
	int near_x,near_y;//near_x,near_y为假设机器人周围的坐标
	for(i=0;i<5;i++)
	{
		test_x=x-roommod[i][0];
		test_y=y-roommod[i][1];
		if(test_x>=0&&test_y>=0&&test_x<m&&test_y<n&&room2r[test_x][test_y][0]==0)//机器人的位置合法?
		{
			for(j=1;j<5;j++)
			{
				near_x=test_x+roommod[j][0];//找出机器人周围所有的位置，判断他们是否合法
				near_y=test_y+roommod[j][1];
				if(near_x>=0&&near_x<m&&near_y>=0&&near_y<n&&room2r[near_x][near_y][0]!=0)
				{
				cannot[x][y][i]=1;//若机器人周围的位置有一个已被占据，则此布局不合法
				}
			}
		}
		else
			if(cannot[x][y][i]==0)
			cannot[x][y][i]=1;
	}//end for
	for(i=0;i<5;i++)
		if(cannot[x][y][i]==0)
			return 1;
		return 0;
}//end testcannot
void Robot::initcannot()
{
	int i,j,k;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			for(k=0;k<5;k++)
				switch(k){
				case 1:if(i+1>=m)
					   { cannot[i][j][k]=-1;
					//cout<<"room( "<<i<<" , "<<j<<" )"<<"can not be occupy with position 2"<<endl;
					   }
					   else cannot[i][j][k]=0;
					   break;
				case 2:if(j+1>=n)
						   cannot[i][j][k]=-1;
					   else cannot[i][j][k]=0;
					   break;if(j+2<n&&i-1>=0&&i+1<m)
						   cannot[i][j][k]=-1;
					   else cannot[i][j][k]=0;
					   break;
				case 3:if(i-1<0)
						   cannot[i][j][k]=-1;
					   else cannot[i][j][k]=0;
					   break;
				case 4:if(j-1<0)
						   cannot[i][j][k]=-1;
					   else cannot[i][j][k]=0;
					   break;
				default:
					cannot[i][j][k]=0;
					break;
			}
}
void Robot::forward()
{
	int i,j,number;
	int near_x,near_y;
	i=0;
	while(cannot[r2dealx][r2dealy][i]!=0&&++i<5);
		r[lastr].x=r2dealx-roommod[i][0];//机器人进栈
		r[lastr].y=r2dealy-roommod[i][1];
		cannot[r2dealx][r2dealy][i]=1;//标记已经试探过了
		room2r[r[lastr].x][r[lastr].y][0]=lastr+1;
		room2r[r[lastr].x][r[lastr].y][1]=r[lastr].x;//机器人占据的房间状态改变
		room2r[r[lastr].x][r[lastr].y][2]=r[lastr].y;
		number=0;//纪录出机器人所在的房间之外受机器人管束的房间个数
		for(j=1;j<5;j++)
		{
			near_x=r[lastr].x+roommod[j][0];
			near_y=r[lastr].y+roommod[j][1];
			if(near_x>=0&&near_x<m&&near_y>=0&&near_y<n)
			{
				room2r[near_x][near_y][0]=lastr+1;//考虑到0代表没有机器人占据
				room2r[near_x][near_y][1]=r[lastr].x;
				room2r[near_x][near_y][2]=r[lastr].y;
				//cout<<near_x<<" , "<<near_y<<":this room is taken care by robot"<<lastr+1<<endl;
				r[lastr].roomx[number]=near_x;
				r[lastr].roomy[number]=near_y;
				number++;
			}
		}
		r[lastr].total=number;
		lastr++;


}
int Robot::go()
{
	//bool end=false;//纪录第一个位置的所有可能是否都已试过
	r2dealx=0;r2dealy=0;
	do{
		if(testcannot(r2dealx,r2dealy))
			forward();
		else 
			if(backward())
				break;//若是从0，0开始向前回溯
	}while(next2deal());//forward & backward都不需要找下一个需要处理的房间next2deal会处理
		if(!next2deal())//
			return 1;
		else return 0;
}//end go
int Robot::backward()
{
	int i,j;
	int p,q;
	lastr--;//机器人出房间
	room2r[r[lastr].x][r[lastr].y][0]=0;
	for(i=0;i<r[lastr].total;i++)
	{
		p=r[lastr].roomx[i];q=r[lastr].roomy[i];
		room2r[p][q][0]=0;
		for(j=0;j<5;j++)
			if(cannot[p][q][i]==1)
				cannot[p][q][i]=0;

	}
	next2deal();
	if(r2dealx==0&&r2dealy==0&&!testcannot(0,0))
		return 1;
	else
		return 0;
	
}
void Robot::initroom()
{
	int i,j;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			room2r[i][j][0]=0;
}

void Robot::initroommod()
{
	roommod[0][0]=0;roommod[0][1]=0;
	roommod[1][0]=-1;roommod[1][1]=0;
	roommod[2][0]=0;roommod[2][1]=-1;
	roommod[3][0]=1;roommod[3][1]=0;
	roommod[4][0]=0;roommod[4][1]=1;
}

void Robot::print()
{
  int i,j,k;
  for(i=0;i<m;i++)
  {
	  for(j=0;j<n;j++)
	  cout<<"--------";
	  cout<<"-"<<endl;
	  for(j=0;j<n;j++)
	  {
		  cout<<"| "<<room2r[i][j][1];
		  k=room2r[i][j][0]-1;
		  if(r[k].x==i&&r[k].y==j)
		  cout<<" @ ";
		  else cout<<" , ";
		  cout<<room2r[i][j][2]<<" ";
	  }
	  cout<<"|"<<endl;
	  for(j=0;j<n;j++)
	  cout<<"|       ";
	  cout<<"|"<<endl;
  }
  for(j=0;j<n;j++)
	  cout<<"--------";
	  cout<<"-"<<endl;
}//end print

void main()
{
	int m,n;
    cout<<"please input room matrix m*n,eg.2*3,4*4"<<endl;
	cout<<"input value of m\n";
	cin>>m;
	cout<<"input value of n\n";
	cin>>n;
    Robot Try(m,n);
	if(Try.go())
	{Try.print();}
	else 
		cout<<"the size given cannot not make an answer"<<endl;
}
/*void Robot::setrmod()
{
	rmod[9][4][2]={{{0,-1},{-1,0}},
	{{0,1},{1,0}},
	{{0,-1},{1,0}},
	{{0,1},{1,0}}
	{{0,-1},{-1,0},{1,0}},
	{{0,-1},{0,1},{-1,0}},
	{{0,1},{-1,0},{1,0}},
	{{0,-1},{0,1},{1,0}},
	{{0,-1},{0,1},{-1,0},{1,0}}
	};
}*/
/*int Robot::selectmod()
{
	testcannot(r2dealx,r2dealy);
	for(int i=0;i<5;i++)
	{
		if(cannot[r2dealx][r2dealy][i]!=0)
			return 1;
	}
	return 0;
}*/