惡心的題啊 。。
先枚舉哪個點是所有人集合的點 再枚舉所有騎士遇見國王的點 如果全部枚舉出來會大大的TLE 經大牛驗證 隻需要枚舉國王周圍的點就可以了+-2 之内
然後各種繁瑣 各種錯誤 騎士有可能不帶着國王一塊走 也可能在他周圍選個點帶着走 先預處理出來每個騎士到國王周圍的最短距離 然後再按上面的枚舉就可以了
考慮的不全面 。。錯了好多個樣例 樣例2,6,19,20 都模拟了一遍。。還好錯在小資料上 可以手算模拟一下 就知道哪錯了 變量名都被我用窮了。。
1 /*
2 ID: shangca2
3 LANG: C++
4 TASK: camelot
5 */
6 #include <iostream>
7 #include<cstdio>
8 #include<cstring>
9 #include<algorithm>
10 #include<stdlib.h>
11 #include<cmath>
12 #include<queue>
13 #define INF 0x3f3f3f
14 using namespace std;
15 int vis[35][35],dis[8][2] = {{2,1},{2,-1},{1,2},{1,-2},{-1,-2},{-1,2},{-2,1},{-2,-1}};
16 typedef struct node
17 {
18 int x,y,num;
19 }st;
20 st qq[10010];
21 int o[35][30][35][30],x[910],y[910],n,m,ans,xx,yy,f[35][35],g;
22 int ff[35][35],di,s;
23 int judge(int x,int y)
24 {
25 if(x<=0||y<=0||x>n||y>m)
26 return 0;
27 return 1;
28 }
29 int bfs(int xi,int yi,int e1,int e2,int flag)
30 {
31 queue<st>q;
32 s=0;int ss=0;
33 memset(vis,0,sizeof(vis));
34 memset(ff,0,sizeof(ff));
35 int i;
36 st tt,te;
37 tt.x = xi;
38 tt.y = yi;
39 tt.num = 0;
40 vis[xi][yi] = 1;
41 q.push(tt);
42 int fff = 0;
43 while(!q.empty())
44 {
45 tt = q.front();
46 q.pop();
47 if(flag&&tt.x==e1&&tt.y==e2)
48 {
49 fff = 1;
50 return tt.num;
51 }
52 o[xi][yi][tt.x][tt.y] = tt.num;
53 o[tt.x][tt.y][xi][yi] = tt.num;
54 if(f[tt.x][tt.y])
55 ss+=tt.num;
56 if(ss>ans)
57 return -1;
58 for(i = 0 ;i < 8 ; i++)
59 {
60 int tx = tt.x+dis[i][0];
61 int ty = tt.y+dis[i][1];
62 if(judge(tx,ty)&&!vis[tx][ty])
63 {
64 te.x = tx;
65 te.y = ty;
66 te.num = tt.num+1;
67 vis[tx][ty] = 1;
68 q.push(te);
69 }
70 }
71 }
72 if(flag&&!fff)
73 return INF;
74 for(i = 1; i <= g ;i++)
75 s+=o[xi][yi][x[i]][y[i]];
76 return s;
77 }
78 int main()
79 {
80 freopen("camelot.in","r",stdin);
81 freopen("camelot.out","w",stdout);
82 int i,j,k,e,ee;
83 for(i =0 ;i <= 33 ; i++)
84 for(j =0 ;j <= 33 ; j++)
85 for(e =0 ;e <= 33 ; e++)
86 for(ee =0 ;ee <= 33 ; ee++)
87 o[i][j][e][ee] = INF;
88 char c;
89 ans = INF;
90 cin>>n>>m;
91 cin>>c>>xx;
92 yy = c-'A'+1;
93 while(cin>>c>>k)
94 {
95 int yg = c-'A'+1;
96 int xg = k;
97 g++;
98 x[g] = xg;
99 y[g] = yg;
100 f[xg][yg] = 1;
101 }
102 int dd[25][2] = {0,0,0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1,2,0,2,1,2,2,2,-1,2,-2,
103 -2,0,-2,1,-2,2,-2,-1,-2,-2,0,2,1,2,-1,2,0,-2,1,-2,-1,-2};
104 for(e = 1; e <= g ;e++)
105 {
106 for(ee = 0 ; ee < 25 ; ee++)
107 {
108 int tx = xx+dd[ee][0];
109 int ty = yy+dd[ee][1];
110 if(judge(tx,ty))
111 {
112 int oo = bfs(x[e],y[e],tx,ty,1);
113 if(oo!=INF)
114 {
115 o[tx][ty][x[e]][y[e]] = oo;
116 o[x[e]][y[e]][tx][ty] = oo;
117 }
118 }
119 }
120 }
121 int dis = INF;
122 for(i = 1; i <= n ; i++)
123 for(j = 1; j <= m ; j++)
124 {
125 if(bfs(i,j,0,0,0)<0)
126 continue;
127 int ko = bfs(i,j,0,0,0);
128 int tns = ko+max(abs(i-xx),abs(j-yy));
129 if(tns<ans)
130 ans = tns;
131
132 if(g==0)
133 ans = ko;
134 for(e = 1; e <= g ;e++)
135 {
136 for(ee = 0 ; ee < 25 ; ee++)
137 {
138 int tx = xx+dd[ee][0];
139 int ty = yy+dd[ee][1];
140 int o1 = o[x[e]][y[e]][tx][ty],o2 = o[i][j][tx][ty],o3 = o[i][j][x[e]][y[e]];
141 if(o1==INF||o2==INF||o3==INF)
142 continue;
143 if(judge(tx,ty)&&ans>(o1+o2-o3+ko+max(abs(tx-xx),abs(ty-yy))))
144 {
145 ans = o1+o2-o3+ko+max(abs(tx-xx),abs(ty-yy));
146 }
147 }
148 }
149 }
150 cout<<ans<<endl;
151 return 0;
152 } View Code