# 3.3.3 Camelot 亚瑟王的宫殿

3.3.3 Camelot 亚瑟王的宫殿

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

``10``

``````#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;
}
``````

``````#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;
}
``````