1
#include<iostream>
2#include<cmath>
3#include<queue>
4#include<algorithm>
5using namespace std;
6#define inf 100000
7
8struct NODE
9
{
10
int row,col;
11
}knight[40*30];
12
13queue<NODE> Q;
14
15struct XX
16{
17 int x,y;
18}offset[]={{-2,-1,},{-2,1},{-1,-2},{-1,2},{1,-2,},{1,2},{2,-1},{2,1}};
19
20int dist[40][40][40][40];
21
22int GG(int i,int j,int x,int y)
23{
24 return max(abs(i-x),abs(j-y));
25}
26
27int R,W;
28void bfs()
29{
30 memset(dist,0,sizeof(dist));
31 for(int r=2;r<R+2;r++)
32 for(int c=2;c<W+2;c++)
33 for(int i=2;i<R+2;i++)
34 for(int j=2;j<W+2;j++)
35 dist[r][c][i][j]=inf;
36
37
for(int r=2;r<R+2;r++){
38 for(int c=2;c<W+2;c++){
39 while(!Q.empty ())Q.pop ();
40 NODE x,y;
41 x.row =r,x.col =c;
42 dist[r][c][r][c]=0;
43 Q.push (x);
44 while(!Q.empty ()){
45 x=Q.front ();Q.pop ();
46 for(int i=0;i<8;i++){
47 int rr,cc;
48 rr=x.row +offset[i].x;
49 cc=x.col +offset[i].y;
50 if( dist[r][c][ rr][cc]> dist[r][c][ x.row ][ x.col ]+1){
51 dist[r][c][rr][cc]=dist[r][c][ x.row ][ x.col ]+1;
52 y.row =rr, y.col =cc;
53 Q.push (y);
54
}
55 }
56 }
57 }
58 }
59}
60
61
62
63
64int main()
65{
66
67
68 while(scanf("%d %d",&R,&W)!=EOF){
69
70 int n=0;
71 char c[2];
72 while(scanf("%s %d",c,&knight[n].row)&&c[0]!='#'){
73 knight[n].col =c[0]-'A'+2;
74 knight[n].row++;
75 n++;
76 }
77 bfs();
78
79 int lowi,lowj,upi,upj,ans=100000000;
80 lowi=max(knight[0].row-2,2);
81 lowj=max(knight[0].col -2,2);
82 upi=min(knight[0].row +2,R+1);
83 upj=min(knight[0].col +2,W+1);
84
85 for(int i=2;i<R+2;i++){
86 for(int j=2;j<W+2;j++){
87 // gather at i j;
88 int sum=0;
89 for(int k=1;k<n;k++)
90 sum+=dist[ knight[k].row ][ knight[k].col ][i][j];
91 if(sum>ans)continue;
92 ans=min(ans,sum+GG(knight[0].row ,knight[0].col ,i,j) );
93 // printf("%d %d\n",sum,ans);
94 for(int ii=lowi;ii<=upi;ii++){
95 for(int jj=lowj;jj<=upj;jj++){
96 // ii jj to carry GG
97 for(int k=1;k<n;k++){
98 // who to carry
99 if(dist[ knight[k].row ][ knight[k].col ][ ii][jj]!=inf ){
100 int t=sum+GG(knight[0].row ,knight[0].col ,ii,jj) +dist[ii][jj][i][j]
101 +dist[ knight[k].row ][ knight[k].col ][ ii][jj]-dist[ knight[k].row ][ knight[k].col ][ i][j];
102 ans=min(ans,t);
103 // printf("%d %d\n",ans,t);
104 }
105 }
106 }
107 }
108 }
109 }
110 //cdgg
111 printf("%d\n",ans);
112 }
113 return 0;
114 }posted on 2009-07-12 10:02
iyixiang 阅读(169)
评论(0) 编辑 收藏 引用 所属分类:
fojpojzojhoj^^^^