记录编号	74822	评测结果	AAAAAAAAAAAAAAAAAAA
题目名称	亚瑟王的宫殿	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.150 s
提交时间	2013-10-26 14:38:11	内存使用	2.85 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;
#define INF 0x7ffffff
const int SIZEL=31,SIZER=27;
class PERSON{
public:
	int x,y;
	int num;
};
int empx,empy;
vector<PERSON> knight;
int ans=INF;
int line,row;
//为便于区分,把国王叫做emperor= =
vector<pair<int,int> > ce[SIZEL][SIZER];//国王法则下的邻接表
vector<pair<int,int> > ck[SIZEL][SIZER];//骑士法则下的邻接表
int de[SIZEL][SIZER]={0};//国王法则的最短路
int dk[SIZEL][SIZER][SIZEL][SIZER]={0};//骑士法则的最短路
deque<pair<int,int> > Q;
void SPFA(vector<pair<int,int> > c[SIZEL][SIZER],int sx,int sy,int d[SIZEL][SIZER]){
	Q.clear();
	bool inq[SIZEL][SIZER]={0};
	int i,j;
	for(i=1;i<=line;i++) for(j=1;j<=row;j++) d[i][j]=INF;
	d[sx][sy]=0;inq[sx][sy]=true;Q.push_back(make_pair(sx,sy));
	int ux,uy,vx,vy;
	#define nowedg c[ux][uy][i]
	while(!Q.empty()){
		ux=Q.front().first;uy=Q.front().second;Q.pop_front();inq[ux][uy]=false;
		for(i=0;i<c[ux][uy].size();i++){
			vx=nowedg.first;vy=nowedg.second;
			if(d[vx][vy]>d[ux][uy]+1){
				d[vx][vy]=d[ux][uy]+1;
				if(!inq[vx][vy]){
					inq[vx][vy]=true;
					Q.push_back(make_pair(vx,vy));
				}
			}
		}
	}
}
void get_mindist(void){
	int i,j;
	for(i=1;i<=line;i++){
		for(j=1;j<=row;j++){
			SPFA(ck,i,j,dk[i][j]);
		}
	}
	SPFA(ce,empx,empy,de);
}
void addedge(int type,int x,int y,int gx,int gy){
	//type=1是国王规则的边,2是骑士规则的边
	if(type==1) ce[x][y].push_back(make_pair(gx,gy));
	else if(type==2) ck[x][y].push_back(make_pair(gx,gy));
}
int emp_dx[9]={0,-1,-1,-1,0,0,1,1,1},emp_dy[9]={0,-1,0,1,-1,1,-1,0,1};//国王的行动方式
int knt_dx[9]={0,1,1,-1,-1,2,2,-2,-2},knt_dy[9]={0,-2,2,-2,2,-1,1,-1,1};//骑士的行动方式
void edge_init(int type,int dx[],int dy[]){
	int i,j,k;
	int gx,gy;
	for(i=1;i<=line;i++){
		for(j=1;j<=row;j++){
			for(k=1;k<=8;k++){
				gx=i+dx[k];gy=j+dy[k];
				if(1<=gx&&gx<=line&&1<=gy&&gy<=row) addedge(type,i,j,gx,gy);
			}
		}
	}
}
void getedge(void){
	edge_init(1,emp_dx,emp_dy);
	edge_init(2,knt_dx,knt_dy);
}
void init(void){
	cin>>line>>row;
	int x;char y;
	int tot=1;
	PERSON temp;
	int kboard[SIZEL][SIZER]={0};
	for(tot=1;!cin.eof();tot++){
		if(cin>>y>>x){
			if(tot==1) empx=line-x+1,empy=y-'A'+1;
			else kboard[line-x+1][y-'A'+1]++;
			tot++;
		}
	}
	int i,j;
	for(i=1;i<=line;i++){
		for(j=1;j<=row;j++){
			if(kboard[i][j]){
				knight.push_back((PERSON){i,j,kboard[i][j]});
			}
		}
	}
	getedge();
	get_mindist();
}
int effect(int gx,int gy,int rx,int ry,int x){//骑士x背国王造成的答案改变量
	int sum=0;
	int kx=knight[x].x,ky=knight[x].y;
	sum-=dk[kx][ky][gx][gy];
	sum+=dk[kx][ky][rx][ry]+dk[rx][ry][gx][gy];
	sum+=de[rx][ry];
	return sum;
}
void calc_g_r(int gx,int gy,int rx,int ry,int sum){
	int i;
	int now;
	for(i=0;i<knight.size();i++){
		now=sum+effect(gx,gy,rx,ry,i);
		ans=min(ans,now);
	}
}
void calc_g(int gx,int gy){
	if(knight.size()==0){
		ans=min(ans,de[gx][gy]);
		return;
	}
	int i,j;
	int kx,ky;
	int sum=0;
	for(i=0;i<knight.size();i++){
		kx=knight[i].x,ky=knight[i].y;
		sum+=dk[kx][ky][gx][gy]*knight[i].num;
	}
	if(sum>ans) return;
	for(i=1;i<=line;i++){
		for(j=1;j<=row;j++){
			calc_g_r(gx,gy,i,j,sum);
		}
	}
}
void work(void){
	int i,j;
	int now;
	for(i=1;i<=line;i++){
		for(j=1;j<=row;j++){
			calc_g(i,j);
		}
	}
	printf("%d\n",ans);
}
int main(){
	freopen("camelot.in","r",stdin);
	freopen("camelot.out","w",stdout);
	init();
	work();
	return 0;
}