1065-robots.cpp

ZOJ 1065 Robots.不算太难,比较麻烦而已吧.

#include<cstdlib>
#include<cstdio>
#include<cmath>
#define INF 10000
char map[31][31],cop[31][31];
//R:robot的数目;T:t...的数目;min_r,min_c最小的行坐标和列坐标;rem剩余的有用的robot数目.
//deb表示debris的数目
int R,T,min_r,min_c,rem,trem,deb,tdeb,min_d;

int fl[9][2]={{-1,-1},{-1, 0},{-1, 1},{ 0,-1},{ 0, 1},{ 1,-1},{ 1, 0},{ 1, 1},{0,0}};
int REM[9],MIN_D[9],F[9],MIN_R[9],MIN_C[9];
//分别表示robot的坐标和teleport locations的坐标.
int rx[50],ry[50],nrx[50],nry[50],tx[20],ty[20],cx[50],cy[50],min[50];
//标记robot和t...是否死亡和已经用过;dead标记我是否已经死亡.
bool used_r[50],used_t[20],c_used[50],dead,tdead;

//输入模块
void input();
//判断(x,y)是否出界
inline bool out(int x,int y);
//求(x,y)到(xx,yy)的距离
inline int dis(int x,int y,int xx,int yy);
//移动robot,其中我的位置在(x,y);返回距离我的最短距离
int move_r(int x,int y);
//复制备份
void copy_1();
void copy_2();

int main()
{
	int num=1;
	//sf表示选择的方向,实际可供选择的决策数目nf
	int i,step,cur_x,cur_y,n_x,n_y,f,sf,nf;
//	freopen("in1.txt","r",stdin);
//	freopen("out1.txt","w+",stdout);
	while(scanf("%d%d",&R,&T)!=EOF && (R || T))
	{
    	if(num>1)
			printf("\n");
		printf("Case %d:\n",num);
		num++;
		//输入
	    input();
        //初始化
		rem=R;	deb=0;	dead=false;
		cur_x=14;	cur_y=14;
	    map[cur_x][cur_y]=-2;
		for(step=1; ;step++)
		{
			//复制备份
		    copy_1();
			sf=-1;
			nf= 0;
			//在9个方向选择
			for(f=0;f<9;f++)
			{
				copy_2();
				n_x=cur_x+fl[f][0];
				n_y=cur_y+fl[f][1];
				//出界或此处被robot占据
				if( out(n_x,n_y) || map[n_x][n_y] >=0 )
					continue;
				//此处是debris.
				if(map[n_x][n_y]==-3)
				{
					//debris的下一个地方出界或者仍是debris
					if( out(n_x+fl[f][0],n_y+fl[f][1]) || map[n_x+fl[f][0]][n_y+fl[f][1]] == -3 )
						continue;
					//下一个位置是robot
					else if( map[n_x+fl[f][0]][n_y+fl[f][1]] >=0 )
					{
						//那个robot被毁,并变成debris
						rem--;
						used_r[map[n_x+fl[f][0]][n_y+fl[f][1]]]=true;						
					}
					map[n_x+fl[f][0]][n_y+fl[f][1]]=-3;
				}
				//我的下一个位置
				map[n_x][n_y]=-2;
				if(f!=8)
					map[cur_x][cur_y]=-1;
				min_d=move_r(n_x,n_y);
				if(dead)
					continue;
				//加入可供选择的决策项目队列
				REM[nf]=rem;
				MIN_D[nf]=min_d;
				F[nf]=f;
				MIN_R[nf]=n_x;
				MIN_C[nf]=n_y;
				nf++;
			}
			//决策
			//有不会导致immediate lose的选择
			if(nf)
			{
				min_r=min_c=INF;
				rem=INF;
				min_d=-1;
				for(i=0;i<nf;i++)
				{
					//选择余下robot数目少的
					if(REM[i]<rem)
					{
						rem=REM[i];
						sf=F[i];
						min_d=MIN_D[i];
						min_r=MIN_R[i];
						min_c=MIN_C[i];
					}
					else if(REM[i]==rem)
					{
						//余下robot数目一样时选择最小距离最大的
						if(MIN_D[i]>min_d)
						{
							sf=F[i];
							min_d=MIN_D[i];
							min_r=MIN_R[i];
							min_c=MIN_C[i];
						}
						else if(MIN_D[i]==min_d)
						{
							//最小距离一样时选择行坐标小的
							if(MIN_R[i]<min_r)
							{
								sf=F[i];
								min_r=MIN_R[i];
								min_c=MIN_C[i];
							}
							else if(MIN_R[i]==min_r)
							{
								//连行坐标也一样时选择列坐标晓得
								if(MIN_C[i]<min_c)
								{
									sf=F[i];
									min_c=MIN_C[i];
								}
							}
						}
					}
				}
				//按最佳决策工作
				copy_2();
			//	printf("最佳决策 sf=%d\n",sf);
			//	print_f(sf);
			//	printf("\n\n");
				//首先我不会撞上robot
				map[cur_x][cur_y]=-1;
				n_x=cur_x+fl[sf][0];
				n_y=cur_y+fl[sf][1];
				//我的下一个位置是debris
				if(map[n_x][n_y]==-3)
				{
					//debris的下一个位置是robot
					if(map[n_x+fl[sf][0]][n_y+fl[sf][1]]>=0)
					{
						rem--;
						used_r[map[n_x+fl[sf][0]][n_y+fl[sf][1]]]=true;				
					}
					map[n_x+fl[sf][0]][n_y+fl[sf][1]]=-3;
				}
				cur_x=n_x;
				cur_y=n_y;				
				map[cur_x][cur_y]=-2;
				//移动robot
				move_r(n_x,n_y);
		  	}
			else
			{
				copy_2();
				//选择向teleport locations求救
				dead=true;
				for(i=0;i<T;i++)
				{
					if(!used_t[i])
					{
						n_x=tx[i];	n_y=ty[i];
						if(map[n_x][n_y]!=-1)
							continue;
						for(f=0;f<8;f++)
						{
							if(!out(n_x+fl[f][0],n_y+fl[f][1])
								&& map[n_x+fl[f][0]][n_y+fl[f][1]]>=0)
								break;
						}
						if(f<8)
							continue;
						//....
						map[cur_x][cur_y]=-1;
						cur_x=n_x;
						cur_y=n_y;
						used_t[i]=true;
						//...
						map[cur_x][cur_y]=-2;
						//
						move_r(cur_x,cur_y);
						printf("Move %d: teleport to (%d,%d)\n",step,cur_x+1,cur_y+1);
						dead=false;
						break;
					}
				}
			}
			//我必死无疑
			if(dead)
			{
				move_r(cur_x,cur_y);
				break;
			}
			if(!rem)
				break;
		}
		if(dead)
		{
			printf("Lost game after making %d moves.\n",step);
			printf("Final position: (%d,%d)\n",cur_x+1,cur_y+1);
			printf("Number of cells with debris: %d\n",deb);
			printf("Number of robots remaining: %d\n",rem);
		}
		else if(!rem)
		{
			printf("Won game after making %d moves.\n",step);
			printf("Final position: (%d,%d)\n",cur_x+1,cur_y+1);
			printf("Number of cells with debris: %d\n",deb);
		}
	}
	return 0;
}

void input()
{
	int i,j;
	//-1表示empty;-2表示me;-3表示debris;其他表示机器人
	for(i=0;i<31;i++)
		for(j=0;j<31;j++)
			map[i][j]=-1;
	for(i=0;i<R;i++)
	{
		scanf("%d%d",&rx[i],&ry[i]);
		rx[i]--;	ry[i]--;
		map[rx[i]][ry[i]]=i;
		used_r[i]=false;
	}
	for(i=0;i<T;i++)
	{
		scanf("%d%d",&tx[i],&ty[i]);
		tx[i]--;	ty[i]--;
		used_t[i]=false;
	}
}

inline bool out(int x,int y)
{
	return x<0 || x>30 || y<0 || y>30;
}

inline int dis(int x,int y,int xx,int yy)
{
	return abs(x-xx)+abs(y-yy);
}

int move_r(int x,int y)
{
	int i,f,ff;
	int ret=INF;
//	copy_1();
	//为每个活着的机器人找到下一个位置
	for(i=0;i<R;i++)
	{
		if(!used_r[i])
		{
			map[rx[i]][ry[i]]=-1;
			nrx[i]=rx[i];
			nry[i]=ry[i];
			min[i]=INF;
			//找出下一步
			for(ff=0;ff<8;ff++)
			{
				//下一步未出界且距离我最小
				if( !out(rx[i]+fl[ff][0],ry[i]+fl[ff][1]) 
					&& dis(rx[i]+fl[ff][0],ry[i]+fl[ff][1],x,y) < min[i] )
				{
					min[i]=dis(rx[i]+fl[ff][0],ry[i]+fl[ff][1],x,y);
					f=ff;
				}
			}	
			nrx[i]=rx[i]+fl[f][0];
			nry[i]=ry[i]+fl[f][1];		
		}
	}
	for(i=0;i<R;i++)
	{
		if(!used_r[i])
		{	
			//下一个位置被debris占据
			if(map[nrx[i]][nry[i]]==-3)
			{
				rem--;
				used_r[i]=true;
			}
			//下一个位置被我占据
			else if(map[nrx[i]][nry[i]]==-2)
			{
				//我已丧命
				dead=true;
				map[nrx[i]][nry[i]]=i;
			}
			//下一个位置被其他robot占据
			else if(map[nrx[i]][nry[i]] >=0)
			{
				used_r[map[nrx[i]][nry[i]]]=true;
				used_r[i]=true;
				rem-=2;
				deb++;
				map[nrx[i]][nry[i]]=-3;
			}
			//下一个位置是空格
			else
				map[nrx[i]][nry[i]]=i;
			rx[i]=nrx[i];
			ry[i]=nry[i];
		}
	}
	for(i=0;i<R;i++)
		if(!used_r[i] && min[i]<ret)
			ret=min[i];
	return ret;
}

void copy_1()
{
	int i,j;
	for(i=0;i<31;i++)
		for(j=0;j<31;j++)
			cop[i][j]=map[i][j];
	for(i=0;i<R;i++)
	{
		cx[i]=rx[i];
		cy[i]=ry[i];
		c_used[i]=used_r[i];
	}
	trem=rem;
	tdeb=deb;
	tdead=dead;
}

void copy_2()
{
	int i,j;
	for(i=0;i<31;i++)
		for(j=0;j<31;j++)
			map[i][j]=cop[i][j];
	for(i=0;i<R;i++)
	{
		used_r[i]=c_used[i];
		rx[i]=cx[i];
		ry[i]=cy[i];
	}
	rem=trem;
	deb=tdeb;
	dead=tdead;
}