3.3.3 Camelot 亚瑟王的宫殿

3.3.3 Camelot 亚瑟王的宫殿

时间: 1ms        内存:64M

描述:

很久以前,亚瑟王和他的骑士习惯每年元旦去庆祝他们的友谊。在回忆中,我们把这些是看作是一个有一人玩的棋盘游戏。有一个国王和若干个骑士被放置在一个由许多方格组成的棋盘上,没有两个骑士在同一个方格内。
这个例子是标准的8*8棋盘
 

国王可以移动到任何一个相邻的方格,从 到 前提是他不掉出棋盘之外。

一个骑士可以从 移动到 但前提是他不掉出棋盘之外。

玩家的任务就是把所有的棋子移动到同一个方格里——用最小的步数。为了完成这个任务,他必须按照上面所说的规则去移动棋子。玩家必须选择一个骑士跟国王一起行动,其他的单独骑士则自己一直走到集中点。骑士和国王一起走的时候,只算一个人走的步数。

写一个程序去计算他们集中在一起的最小步数,而且玩家必须自己找出这个集中点。当然,这些棋子可以在棋盘的任何地方集合。

输入:

第一行: 两个用空格隔开的整数:R,C 分别为棋盘行和列的长。不超过26列,40行。
第二行..结尾: 输入文件包含了一些有空格隔开的字母/数字对,一行有一个或以上。第一对为国王的位置,接下来是骑士的位置。可能没有骑士,也可能整个棋盘都是骑士。行从1开始,列从大写字母A开始。

输出:

单独一行表示棋子集中在一个方格的最小步数。

示例输入:

8 8
D 4
A 3 A 8
H 1 H 8

示例输出:

10

提示:

参考答案(内存最优[8400]):

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

typedef struct
{
	int x;
	int y;
	int d;
}data;

typedef struct
{
	int x;
	int y;
}pos;

int row[8]={1,2,-1,2,1,-2,-1,-2};
int col[8]={2,1,2,-1,-2,1,-2,-1};

int r,c;
int d[45][30][45][30];
pos king,knight[1050];
int cntknight;
int res;

void bfs()
{
	queue<data> q;
	data cur,curc;
	bool isvis[45][30];
	int i,j,k,l;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
			for(k=1;k<=r;k++)
				for(l=1;l<=c;l++)
					d[i][j][k][l]=10000000;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
		{
			while(!q.empty())
				q.pop();
			for(k=1;k<=r;k++)
				for(l=1;l<=c;l++)
					isvis[k][l]=false;
			cur.x=i;
			cur.y=j;
			cur.d=0;
			isvis[i][j]=true;
			d[i][j][i][j]=0;
			q.push(cur);
			while(!q.empty())
			{
				cur=q.front();
				q.pop();
				for(k=0;k<8;k++)
				{
					curc.x=cur.x+row[k];
					curc.y=cur.y+col[k];
					if(curc.x>=1&&curc.x<=r&&curc.y>=1&&curc.y<=c&&isvis[curc.x][curc.y]==false)
					{
						d[i][j][curc.x][curc.y]=cur.d+1;
						curc.d=d[i][j][curc.x][curc.y];
						q.push(curc);
						isvis[curc.x][curc.y]=true;
					}
				}
			}
		}
}

int main()
{
	int i,j,k;
	int tmpx,tmpy;
	int maxx,minx,maxy,miny;
	int x;
	char y;
	int minn,sum,now,maxn,maxm;
	cin>>r>>c;
	cin>>y>>x;
	king.x=x;
	king.y=y-'A'+1;
	while(cin>>y>>x)
	{
		knight[cntknight].x=x;
		knight[cntknight].y=y-'A'+1;
		cntknight++;
	}
	bfs();
	res=2100000000;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
		{
			minn=2100000000;
			sum=0;
			for(k=0;k<cntknight;k++)
				sum+=d[i][j][knight[k].x][knight[k].y];
			maxn=fabs(king.x-i);
			if(fabs(king.y-j)>maxn)
				maxn=fabs(king.y-j);
			if(sum+maxn<minn)
				minn=sum+maxn;
			maxx=1;
			if(king.x-2>maxx)
				maxx=king.x-2;
			minx=r;
			if(king.x+2<minx)
				minx=king.x+2;
			for(tmpx=maxx;tmpx<=minx;tmpx++)
			{
				maxy=1;
				if(king.y-2>maxy)
					maxy=king.y-2;
				miny=c;
				if(king.y+2<miny)
					miny=king.y+2;
				for(tmpy=maxy;tmpy<=miny;tmpy++)
					for(k=0;k<cntknight;k++)
					{
						maxm=fabs(king.x-tmpx);
						if(fabs(king.y-tmpy)>maxm)
							maxm=fabs(king.y-tmpy);
						now=sum-d[i][j][knight[k].x][knight[k].y]
							+d[knight[k].x][knight[k].y][tmpx][tmpy]+d[tmpx][tmpy][i][j]+maxm;
						if(now<minn)
							minn=now;
					}
			}
			if(minn<res)
				res=minn;
		}
	cout<<res<<endl;
	return 0;
}

参考答案(时间最优[576]):

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

typedef struct
{
	int x;
	int y;
	int d;
}data;

typedef struct
{
	int x;
	int y;
}pos;

int row[8]={1,2,-1,2,1,-2,-1,-2};
int col[8]={2,1,2,-1,-2,1,-2,-1};

int r,c;
int d[45][30][45][30];
pos king,knight[1050];
int cntknight;
int res;

void bfs()
{
	queue<data> q;
	data cur,curc;
	bool isvis[45][30];
	int i,j,k,l;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
			for(k=1;k<=r;k++)
				for(l=1;l<=c;l++)
					d[i][j][k][l]=10000000;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
		{
			while(!q.empty())
				q.pop();
			for(k=1;k<=r;k++)
				for(l=1;l<=c;l++)
					isvis[k][l]=false;
			cur.x=i;
			cur.y=j;
			cur.d=0;
			isvis[i][j]=true;
			d[i][j][i][j]=0;
			q.push(cur);
			while(!q.empty())
			{
				cur=q.front();
				q.pop();
				for(k=0;k<8;k++)
				{
					curc.x=cur.x+row[k];
					curc.y=cur.y+col[k];
					if(curc.x>=1&&curc.x<=r&&curc.y>=1&&curc.y<=c&&isvis[curc.x][curc.y]==false)
					{
						d[i][j][curc.x][curc.y]=cur.d+1;
						curc.d=d[i][j][curc.x][curc.y];
						q.push(curc);
						isvis[curc.x][curc.y]=true;
					}
				}
			}
		}
}

int main()
{
	int i,j,k;
	int tmpx,tmpy;
	int maxx,minx,maxy,miny;
	int x;
	char y;
	int minn,sum,now,maxn,maxm;
	cin>>r>>c;
	cin>>y>>x;
	king.x=x;
	king.y=y-'A'+1;
	while(cin>>y>>x)
	{
		knight[cntknight].x=x;
		knight[cntknight].y=y-'A'+1;
		cntknight++;
	}
	bfs();
	res=2100000000;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
		{
			minn=2100000000;
			sum=0;
			for(k=0;k<cntknight;k++)
				sum+=d[i][j][knight[k].x][knight[k].y];
			maxn=fabs(king.x-i);
			if(fabs(king.y-j)>maxn)
				maxn=fabs(king.y-j);
			if(sum+maxn<minn)
				minn=sum+maxn;
			maxx=1;
			if(king.x-2>maxx)
				maxx=king.x-2;
			minx=r;
			if(king.x+2<minx)
				minx=king.x+2;
			for(tmpx=maxx;tmpx<=minx;tmpx++)
			{
				maxy=1;
				if(king.y-2>maxy)
					maxy=king.y-2;
				miny=c;
				if(king.y+2<miny)
					miny=king.y+2;
				for(tmpy=maxy;tmpy<=miny;tmpy++)
					for(k=0;k<cntknight;k++)
					{
						maxm=fabs(king.x-tmpx);
						if(fabs(king.y-tmpy)>maxm)
							maxm=fabs(king.y-tmpy);
						now=sum-d[i][j][knight[k].x][knight[k].y]
							+d[knight[k].x][knight[k].y][tmpx][tmpy]+d[tmpx][tmpy][i][j]+maxm;
						if(now<minn)
							minn=now;
					}
			}
			if(minn<res)
				res=minn;
		}
	cout<<res<<endl;
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注