记录编号	368912	评测结果	AAAAAAAAAAAAAAAAAAA
题目名称	亚瑟王的宫殿	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	0.247 s
提交时间	2017-02-07 15:56:57	内存使用	10.11 MiB

//874
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;
const int nmax=40;
const int pmax=910;
const int INF=1<<16;

int cnt;
int n,m;
int ans;
int kingdis[nmax][nmax]={0};
int knightdis[nmax][nmax]={0};
int dis[nmax][nmax][nmax][nmax]={0};
int op[8][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};

class poi{
public:
	int x;
	int y;
};
poi knight[pmax];
poi king;

void PreDo(){
	memset(knightdis,0,sizeof(knightdis));
	memset(kingdis,0,sizeof(kingdis));
	ans=INF;
	cnt=0;
	scanf("%d%d",&n,&m);
	char tmpn;
	int  tmpm;
	cin>>tmpn>>tmpm;
//	scanf("%c%d",&tmpn,&tmpm);
	king.x=tmpm;
	king.y=tmpn-'A'+1;
	while(cin>>tmpn>>tmpm){
		cnt++;
		knight[cnt].x=tmpm;
		knight[cnt].y=tmpn-'A'+1;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=1;k<=n;k++)
				for(int l=1;l<=m;l++)
					dis[i][j][k][l]=INF;
}

bool Check(int x,int y){
	bool tag=1;
	if(x<1||x>n) tag=0;
	if(y<1||y>m) tag=0;
	return tag;
}

int vis[nmax][nmax]={0};
void BFS(int x,int y){
	queue<poi > Q;
	memset(vis,0,sizeof(vis));
	while(!Q.empty()) Q.pop();
	Q.push((poi){x,y});
	vis[x][y]=1;
	dis[x][y][x][y]=0;
	while(!Q.empty()){
		poi tmpx=Q.front();
//		printf("%d\n",dis[x][y][tmpx.x][tmpx.y]);
		Q.pop();
		for(int i=0;i<8;i++){
			poi aft;
			aft.x=tmpx.x+op[i][0];
			aft.y=tmpx.y+op[i][1];
			if(Check(aft.x,aft.y)&&!vis[aft.x][aft.y]){
				dis[x][y][aft.x][aft.y]=dis[x][y][tmpx.x][tmpx.y]+1;
				Q.push(aft);
				vis[aft.x][aft.y]=1;
			}
		}
	}
	return ;
}

void Col(){

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			int tmpx=abs((double)king.x-i);
			int tmpy=abs((double)king.y-j);
			kingdis[i][j]=max(tmpx,tmpy);
		}
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			BFS(i,j);		
				
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int id=1;id<=cnt;id++){
				knightdis[i][j]+=dis[knight[id].x][knight[id].y][i][j];
			}
			
	if(!cnt)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				ans=min(ans,kingdis[i][j]);
	
	for(int id=1;id<=cnt;id++)
	for(int ix=king.x-2;ix<=king.x+2;ix++)
	for(int iy=king.y-2;iy<=king.y+2;iy++)
	if(Check(ix,iy))
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		ans=min(ans,knightdis[i][j]-
					dis[i][j][knight[id].x][knight[id].y]+
					dis[ix][iy][i][j]+
					dis[ix][iy][knight[id].x][knight[id].y]+
					kingdis[ix][iy]);			
	
	printf("%d\n",ans);
	return ;
}

int main(){
	freopen("camelot.in","r",stdin);
	freopen("camelot.out","w",stdout);
	PreDo();
	Col();
	return 0;
}