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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。