记录编号	458440	评测结果	AAAAAAAAAAAAAAAAAAA
题目名称	亚瑟王的宫殿	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	0.252 s
提交时间	2017-10-11 11:23:22	内存使用	4.22 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector> 
#include<cmath>

using namespace std;

int n,m,knt,ki[1010],dis[1010][1010],sm[1010],ans=0x3fffffff;
int dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};

vector<int>e[1010];

void init()
{
	for(int i=0;i<=n-1;i++){
		for(int j=0;j<=m-1;j++){
			for(int k=0;k<8;k++){
				int nx=i+dx[k];
				int ny=j+dy[k];
				if(nx>=n||nx<0||ny>=m||ny<0) continue;
				e[i*m+j].push_back(nx*m+ny);
			}
		}
	}
}

void spfa(int pos)
{
	queue<int>q;
	int inq[1010];
	memset(inq,0,sizeof(inq));
	q.push(pos);
	dis[pos][pos]=0;
	inq[pos]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=0;i<e[u].size();i++){
			int to=e[u][i];
			if(dis[pos][to]>dis[pos][u]+1){
				dis[pos][to]=dis[pos][u]+1;
				if(!inq[to]){
					inq[to]=1;
					q.push(to);
				}
			}
		}
	}
	return;
}

int main()
{
//	freopen("1.txt","r",stdin);
	freopen("camelot.in","r",stdin);
	freopen("camelot.out","w",stdout);
	scanf("%d%d",&n,&m);
	char a;
	int b;
	while(cin>>a>>b){
		int c=a-'A';
		ki[knt++]=(b-1)*m+c;
	}
	init();
	memset(dis,0x3f,sizeof(dis));
	for(int i=0;i<=n*m-1;i++) spfa(i);
//	for(int i=0;i<=n*m-1;i++){
//		for(int j=0;j<=n*m-1;j++){
//			int y1=i%m,y2=j%m;
//			int x1=(i-y1)/m,x2=(j-y2)/m;
//			cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<dis[i][j]<<endl;
//		}
//	}
	for(int i=0;i<=n*m-1;i++){
		for(int j=1;j<=knt-1;j++){
			sm[i]+=dis[i][ki[j]];
		}
		if(sm[i]<0||sm[i]>=1e9) sm[i]=1e9;
		int y1=i%m,y2=ki[0]%m;
		int x1=(i-y1)/m,x2=(ki[0]-y2)/m;
		ans=min(ans,sm[i]+max((int)abs(x1-x2),(int)abs(y1-y2)));
	}
	for(int zd=0;zd<=n*m-1;zd++){
		if(sm[zd]>=1e9) continue;
		for(int qs=1;qs<=knt-1;qs++){
			int temp=sm[zd]-dis[zd][ki[qs]];
			if(temp>=ans) continue;//神tm剪枝%%% 
			for(int hm=0;hm<=n*m-1;hm++){
				int t=temp;
				int y1=hm%m,y2=ki[0]%m;
				int x1=(hm-y1)/m,x2=(ki[0]-y2)/m;
				t+=dis[ki[qs]][hm];
				t+=max((int)abs(x1-x2),(int)abs(y1-y2));
				t+=dis[hm][zd];
				ans=min(ans,t);
			}
		}
	}
	printf("%d",ans);
	return 0;
}