挺有意思但是代码巨恶心的一道最短路搜索题。
因为图中的结点太多，应当首先考虑把隐式图转化成显式图，即对地图中可以相互连通的点之间连边，建立一个新图（由于每步不需要每个鬼都移动，所以每个点需要向自己也连一条边）。设d[i][j][k]为走到“A在结点i，B在结点j，C在结点k”的状态需要多少步，直接bfs即可。
注意由于鬼的个数不确定，为了减少特判，需要留出三个虚节点，把多出来的鬼的起点和终点都设到同一个虚节点上。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int N=16+2;
5 struct D {int a[3];};
6 struct E {int v,nxt;} e[1000000];
7 int rt[N][N],d[200][200][200],n,m,k,tot,ne,hd[200],bg[3],ed[3];
8 char s[N][N];
9 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
10 bool ok(int* u,int* v) {
11 if(v[0]==v[1]||v[1]==v[2]||v[2]==v[0])return 0;
12 if(u[0]==v[1]&&u[1]==v[0])return 0;
13 if(u[1]==v[2]&&u[2]==v[1])return 0;
14 if(u[2]==v[0]&&u[0]==v[2])return 0;
15 return 1;
16 }
17
18 int bfs() {
19 int u[3],v[3];
20 queue<D> q;
21 q.push({bg[0],bg[1],bg[2]}),d[bg[0]][bg[1]][bg[2]]=0;
22 while(!q.empty()) {
23 memcpy(u,q.front().a,sizeof u),q.pop();
24 if(u[0]==ed[0]&&u[1]==ed[1]&&u[2]==ed[2])return d[u[0]][u[1]][u[2]];
25 for(int i=hd[u[0]]; ~i; i=e[i].nxt)
26 for(int j=hd[u[1]]; ~j; j=e[j].nxt)
27 for(int k=hd[u[2]]; ~k; k=e[k].nxt) {
28 v[0]=e[i].v,v[1]=e[j].v,v[2]=e[k].v;
29 if(ok(u,v)&&!~d[v[0]][v[1]][v[2]]) {
30 d[v[0]][v[1]][v[2]]=d[u[0]][u[1]][u[2]]+1;
31 q.push({v[0],v[1],v[2]});
32 }
33 }
34 }
35 return -1;
36 }
37
38 int main() {
39 while(scanf("%d%d%d",&m,&n,&k)&&n) {
40 scanf(" ");
41 memset(hd,-1,sizeof hd),ne=0,tot=3;
42 for(int i=0; i<3; ++i)bg[i]=ed[i]=i;
43 addedge(0,0),addedge(1,1),addedge(2,2);
44 for(int i=0; i<n; ++i)gets(s[i]);
45 for(int i=1; i<n-1; ++i)for(int j=1; j<m-1; ++j)if(s[i][j]!='#') {
46 rt[i][j]=tot++;
47 addedge(rt[i][j],rt[i][j]);
48 if(s[i-1][j]!='#') {
49 addedge(rt[i][j],rt[i-1][j]);
50 addedge(rt[i-1][j],rt[i][j]);
51 }
52 if(s[i][j-1]!='#') {
53 addedge(rt[i][j],rt[i][j-1]);
54 addedge(rt[i][j-1],rt[i][j]);
55 }
56 if(isupper(s[i][j]))bg[s[i][j]-'A']=rt[i][j];
57 else if(islower(s[i][j]))ed[s[i][j]-'a']=rt[i][j];
58 }
59 for(int i=0; i<tot; ++i)for(int j=0; j<tot; ++j)for(int k=0; k<tot; ++k)d[i][j][k]=-1;
60 printf("%d\n",bfs());
61 }
62 return 0;
63 }
bfs
这个代码跑了1000+ms，我们可以继续优化。
优化一：由于把一步移动撤回的规则和正向移动的规则是一样的，因此可以把bfs改成双向的，即6个鬼同时从起点和终点出发直到相遇，这样可以降低bfs树的深度，少扩展一些结点。方法是将d数组多开一维，代表每个状态是正向转移来的还是反向转移来的。如果一个状态的反状态(对应鬼的位置均相等，bfs方向相反)，则两状态的d值相加即为最短距离。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int N=16+2;
5 struct D {int f,a[3];};
6 struct E {int v,nxt;} e[1000000];
7 int rt[N][N],d[2][200][200][200],n,m,k,tot,ne,hd[200],bg[3],ed[3];
8 char s[N][N];
9 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
10 bool ok(int* u,int* v) {
11 if(v[0]==v[1]||v[1]==v[2]||v[2]==v[0])return 0;
12 if(u[0]==v[1]&&u[1]==v[0])return 0;
13 if(u[1]==v[2]&&u[2]==v[1])return 0;
14 if(u[2]==v[0]&&u[0]==v[2])return 0;
15 return 1;
16 }
17
18 int bfs() {
19 int u[3],v[3],f;
20 queue<D> q;
21 q.push({0,bg[0],bg[1],bg[2]}),d[0][bg[0]][bg[1]][bg[2]]=0;
22 q.push({1,ed[0],ed[1],ed[2]}),d[1][ed[0]][ed[1]][ed[2]]=0;
23 while(!q.empty()) {
24 memcpy(u,q.front().a,sizeof u),f=q.front().f,q.pop();
25 if(~d[f^1][u[0]][u[1]][u[2]])return d[f][u[0]][u[1]][u[2]]+d[f^1][u[0]][u[1]][u[2]];
26 for(int i=hd[u[0]]; ~i; i=e[i].nxt)
27 for(int j=hd[u[1]]; ~j; j=e[j].nxt)
28 for(int k=hd[u[2]]; ~k; k=e[k].nxt) {
29 v[0]=e[i].v,v[1]=e[j].v,v[2]=e[k].v;
30 if(ok(u,v)&&!~d[f][v[0]][v[1]][v[2]]) {
31 d[f][v[0]][v[1]][v[2]]=d[f][u[0]][u[1]][u[2]]+1;
32 q.push({f,v[0],v[1],v[2]});
33 }
34 }
35 }
36 return -1;
37 }
38
39 int main() {
40 while(scanf("%d%d%d",&m,&n,&k)&&n) {
41 scanf(" ");
42 memset(hd,-1,sizeof hd),ne=0,tot=3;
43 for(int i=0; i<3; ++i)bg[i]=ed[i]=i;
44 addedge(0,0),addedge(1,1),addedge(2,2);
45 for(int i=0; i<n; ++i)gets(s[i]);
46 for(int i=1; i<n-1; ++i)for(int j=1; j<m-1; ++j)if(s[i][j]!='#') {
47 rt[i][j]=tot++;
48 addedge(rt[i][j],rt[i][j]);
49 if(s[i-1][j]!='#') {
50 addedge(rt[i][j],rt[i-1][j]);
51 addedge(rt[i-1][j],rt[i][j]);
52 }
53 if(s[i][j-1]!='#') {
54 addedge(rt[i][j],rt[i][j-1]);
55 addedge(rt[i][j-1],rt[i][j]);
56 }
57 if(isupper(s[i][j]))bg[s[i][j]-'A']=rt[i][j];
58 else if(islower(s[i][j]))ed[s[i][j]-'a']=rt[i][j];
59 }
60 for(int i=0; i<tot; ++i)for(int j=0; j<tot; ++j)for(int k=0; k<tot; ++k)d[0][i][j][k]=d[1][i][j][k]=-1;
61 printf("%d\n",bfs());
62 }
63 return 0;
64 }
bfs(双向)
跑了600+ms，感觉也没快多少~~
优化二：可以考虑用A*算法，新开一个h数组记录每个节点分别到a,b,c结点的最短距离(可用bfs预处理)，则当前状态(i,j,k)到(a,b,c)的最短距离不超过f[i][j][k]=d[i][j][k]+max(h[a][i],h[b][j],h[c][k])，选择把原来的队列换成优先队列，每次取出f值最小的结点进行扩展即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int N=16+2;
5 struct E {int v,nxt;} e[1000000];
6 int rt[N][N],d[200][200][200],h[3][200],n,m,k,tot,ne,hd[200],bg[3],ed[3];
7 char s[N][N];
8 struct D {
9 int a[3];
10 bool operator<(const D& b)const {
11 return d[a[0]][a[1]][a[2]]+max(h[0][a[0]],max(h[1][a[1]],h[2][a[2]]))
12 >d[b.a[0]][b.a[1]][b.a[2]]+max(h[0][b.a[0]],max(h[1][b.a[1]],h[2][b.a[2]]));
13 }
14 };
15 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
16 bool ok(int* u,int* v) {
17 if(v[0]==v[1]||v[1]==v[2]||v[2]==v[0])return 0;
18 if(u[0]==v[1]&&u[1]==v[0])return 0;
19 if(u[1]==v[2]&&u[2]==v[1])return 0;
20 if(u[2]==v[0]&&u[0]==v[2])return 0;
21 return 1;
22 }
23
24 void bfs(int S,int* d) {
25 int u,v;
26 queue<int> q;
27 for(int i=0; i<tot; ++i)d[i]=-1;
28 q.push(S),d[S]=0;
29 while(!q.empty()) {
30 u=q.front(),q.pop();
31 for(int i=hd[u]; ~i; i=e[i].nxt) {
32 v=e[i].v;
33 if(!~d[v])d[v]=d[u]+1,q.push(v);
34 }
35 }
36 }
37
38 int Astar() {
39 int u[3],v[3];
40 priority_queue<D> q;
41 d[bg[0]][bg[1]][bg[2]]=0,q.push({bg[0],bg[1],bg[2]});
42 while(!q.empty()) {
43 memcpy(u,q.top().a,sizeof u),q.pop();
44 if(u[0]==ed[0]&&u[1]==ed[1]&&u[2]==ed[2])return d[u[0]][u[1]][u[2]];
45 for(int i=hd[u[0]]; ~i; i=e[i].nxt)
46 for(int j=hd[u[1]]; ~j; j=e[j].nxt)
47 for(int k=hd[u[2]]; ~k; k=e[k].nxt) {
48 v[0]=e[i].v,v[1]=e[j].v,v[2]=e[k].v;
49 if(ok(u,v)&&!~d[v[0]][v[1]][v[2]]) {
50 d[v[0]][v[1]][v[2]]=d[u[0]][u[1]][u[2]]+1;
51 q.push({v[0],v[1],v[2]});
52 }
53 }
54 }
55 return -1;
56 }
57
58 int main() {
59 while(scanf("%d%d%d",&m,&n,&k)&&n) {
60 scanf(" ");
61 memset(hd,-1,sizeof hd),ne=0,tot=3;
62 for(int i=0; i<3; ++i)bg[i]=ed[i]=i;
63 addedge(0,0),addedge(1,1),addedge(2,2);
64 for(int i=0; i<n; ++i)gets(s[i]);
65 for(int i=1; i<n-1; ++i)for(int j=1; j<m-1; ++j)if(s[i][j]!='#') {
66 rt[i][j]=tot++;
67 addedge(rt[i][j],rt[i][j]);
68 if(s[i-1][j]!='#') {
69 addedge(rt[i][j],rt[i-1][j]);
70 addedge(rt[i-1][j],rt[i][j]);
71 }
72 if(s[i][j-1]!='#') {
73 addedge(rt[i][j],rt[i][j-1]);
74 addedge(rt[i][j-1],rt[i][j]);
75 }
76 if(isupper(s[i][j]))bg[s[i][j]-'A']=rt[i][j];
77 else if(islower(s[i][j]))ed[s[i][j]-'a']=rt[i][j];
78 }
79 for(int i=0; i<tot; ++i)for(int j=0; j<tot; ++j)for(int k=0; k<tot; ++k)d[i][j][k]=-1;
80 for(int i=0; i<3; ++i)bfs(ed[i],h[i]);
81 printf("%d\n",Astar());
82 }
83 return 0;
84 }
A*
我用A*算法跑样例的速度明显快了好几个档次，但提交上去却依旧跑了400+ms，看来A*终究逃不过被卡的命运~~