挺有意思但是代码巨恶心的一道最短路搜索题。
因为图中的结点太多，应当首先考虑把隐式图转化成显式图，即对地图中可以相互连通的点之间连边，建立一个新图（由于每步不需要每个鬼都移动，所以每个点需要向自己也连一条边）。设d[i][j][k]为走到“A在结点i，B在结点j，C在结点k”的状态需要多少步，直接bfs即可。
注意由于鬼的个数不确定，为了减少特判，需要留出三个虚节点，把多出来的鬼的起点和终点都设到同一个虚节点上。
（代码刚写完后发现样例的答案比正确的少了2，检查了好久才发现自己建图的时候tot多加了1...）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+;
struct D {int a[];};
struct E {int v,nxt;} e[];
int rt[N][N],d[][][],n,m,k,tot,ne,hd[],bg[],ed[];
char s[N][N];
void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
bool ok(int* u,int* v) {
if(v[]==v[]||v[]==v[]||v[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
return ;
} int bfs() {
int u[],v[];
queue<D> q;
q.push({bg[],bg[],bg[]}),d[bg[]][bg[]][bg[]]=;
while(!q.empty()) {
memcpy(u,q.front().a,sizeof u),q.pop();
if(u[]==ed[]&&u[]==ed[]&&u[]==ed[])return d[u[]][u[]][u[]];
for(int i=hd[u[]]; ~i; i=e[i].nxt)
for(int j=hd[u[]]; ~j; j=e[j].nxt)
for(int k=hd[u[]]; ~k; k=e[k].nxt) {
v[]=e[i].v,v[]=e[j].v,v[]=e[k].v;
if(ok(u,v)&&!~d[v[]][v[]][v[]]) {
d[v[]][v[]][v[]]=d[u[]][u[]][u[]]+;
q.push({v[],v[],v[]});
}
}
}
return -;
} int main() {
while(scanf("%d%d%d",&m,&n,&k)&&n) {
scanf(" ");
memset(hd,-,sizeof hd),ne=,tot=;
for(int i=; i<; ++i)bg[i]=ed[i]=i;
addedge(,),addedge(,),addedge(,);
for(int i=; i<n; ++i)gets(s[i]);
for(int i=; i<n-; ++i)for(int j=; j<m-; ++j)if(s[i][j]!='#') {
rt[i][j]=tot++;
addedge(rt[i][j],rt[i][j]);
if(s[i-][j]!='#') {
addedge(rt[i][j],rt[i-][j]);
addedge(rt[i-][j],rt[i][j]);
}
if(s[i][j-]!='#') {
addedge(rt[i][j],rt[i][j-]);
addedge(rt[i][j-],rt[i][j]);
}
if(isupper(s[i][j]))bg[s[i][j]-'A']=rt[i][j];
else if(islower(s[i][j]))ed[s[i][j]-'a']=rt[i][j];
}
for(int i=; i<tot; ++i)for(int j=; j<tot; ++j)for(int k=; k<tot; ++k)d[i][j][k]=-;
printf("%d\n",bfs());
}
return ;
}
bfs
这个代码跑了1000+ms，我们可以继续优化。
优化一：由于把一步移动撤回的规则和正向移动的规则是一样的，因此可以把bfs改成双向的，即6个鬼同时从起点和终点出发直到相遇，这样可以降低bfs树的深度，少扩展一些结点。方法是将d数组多开一维，代表每个状态是正向转移来的还是反向转移来的。如果一个状态的反状态(对应鬼的位置均相等，bfs方向相反)，则两状态的d值相加即为最短距离。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+;
struct D {int f,a[];};
struct E {int v,nxt;} e[];
int rt[N][N],d[][][][],n,m,k,tot,ne,hd[],bg[],ed[];
char s[N][N];
void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
bool ok(int* u,int* v) {
if(v[]==v[]||v[]==v[]||v[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
return ;
} int bfs() {
int u[],v[],f;
queue<D> q;
q.push({,bg[],bg[],bg[]}),d[][bg[]][bg[]][bg[]]=;
q.push({,ed[],ed[],ed[]}),d[][ed[]][ed[]][ed[]]=;
while(!q.empty()) {
memcpy(u,q.front().a,sizeof u),f=q.front().f,q.pop();
if(~d[f^][u[]][u[]][u[]])return d[f][u[]][u[]][u[]]+d[f^][u[]][u[]][u[]];
for(int i=hd[u[]]; ~i; i=e[i].nxt)
for(int j=hd[u[]]; ~j; j=e[j].nxt)
for(int k=hd[u[]]; ~k; k=e[k].nxt) {
v[]=e[i].v,v[]=e[j].v,v[]=e[k].v;
if(ok(u,v)&&!~d[f][v[]][v[]][v[]]) {
d[f][v[]][v[]][v[]]=d[f][u[]][u[]][u[]]+;
q.push({f,v[],v[],v[]});
}
}
}
return -;
} int main() {
while(scanf("%d%d%d",&m,&n,&k)&&n) {
scanf(" ");
memset(hd,-,sizeof hd),ne=,tot=;
for(int i=; i<; ++i)bg[i]=ed[i]=i;
addedge(,),addedge(,),addedge(,);
for(int i=; i<n; ++i)gets(s[i]);
for(int i=; i<n-; ++i)for(int j=; j<m-; ++j)if(s[i][j]!='#') {
rt[i][j]=tot++;
addedge(rt[i][j],rt[i][j]);
if(s[i-][j]!='#') {
addedge(rt[i][j],rt[i-][j]);
addedge(rt[i-][j],rt[i][j]);
}
if(s[i][j-]!='#') {
addedge(rt[i][j],rt[i][j-]);
addedge(rt[i][j-],rt[i][j]);
}
if(isupper(s[i][j]))bg[s[i][j]-'A']=rt[i][j];
else if(islower(s[i][j]))ed[s[i][j]-'a']=rt[i][j];
}
for(int i=; i<tot; ++i)for(int j=; j<tot; ++j)for(int k=; k<tot; ++k)d[][i][j][k]=d[][i][j][k]=-;
printf("%d\n",bfs());
}
return ;
}
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值最小的结点进行扩展即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+;
struct E {int v,nxt;} e[];
int rt[N][N],d[][][],h[][],n,m,k,tot,ne,hd[],bg[],ed[];
char s[N][N];
struct D {
int a[];
bool operator<(const D& b)const {
return d[a[]][a[]][a[]]+max(h[][a[]],max(h[][a[]],h[][a[]]))
>d[b.a[]][b.a[]][b.a[]]+max(h[][b.a[]],max(h[][b.a[]],h[][b.a[]]));
}
};
void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
bool ok(int* u,int* v) {
if(v[]==v[]||v[]==v[]||v[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
if(u[]==v[]&&u[]==v[])return ;
return ;
} void bfs(int S,int* d) {
int u,v;
queue<int> q;
for(int i=; i<tot; ++i)d[i]=-;
q.push(S),d[S]=;
while(!q.empty()) {
u=q.front(),q.pop();
for(int i=hd[u]; ~i; i=e[i].nxt) {
v=e[i].v;
if(!~d[v])d[v]=d[u]+,q.push(v);
}
}
} int Astar() {
int u[],v[];
priority_queue<D> q;
d[bg[]][bg[]][bg[]]=,q.push({bg[],bg[],bg[]});
while(!q.empty()) {
memcpy(u,q.top().a,sizeof u),q.pop();
if(u[]==ed[]&&u[]==ed[]&&u[]==ed[])return d[u[]][u[]][u[]];
for(int i=hd[u[]]; ~i; i=e[i].nxt)
for(int j=hd[u[]]; ~j; j=e[j].nxt)
for(int k=hd[u[]]; ~k; k=e[k].nxt) {
v[]=e[i].v,v[]=e[j].v,v[]=e[k].v;
if(ok(u,v)&&!~d[v[]][v[]][v[]]) {
d[v[]][v[]][v[]]=d[u[]][u[]][u[]]+;
q.push({v[],v[],v[]});
}
}
}
return -;
} int main() {
while(scanf("%d%d%d",&m,&n,&k)&&n) {
scanf(" ");
memset(hd,-,sizeof hd),ne=,tot=;
for(int i=; i<; ++i)bg[i]=ed[i]=i;
addedge(,),addedge(,),addedge(,);
for(int i=; i<n; ++i)gets(s[i]);
for(int i=; i<n-; ++i)for(int j=; j<m-; ++j)if(s[i][j]!='#') {
rt[i][j]=tot++;
addedge(rt[i][j],rt[i][j]);
if(s[i-][j]!='#') {
addedge(rt[i][j],rt[i-][j]);
addedge(rt[i-][j],rt[i][j]);
}
if(s[i][j-]!='#') {
addedge(rt[i][j],rt[i][j-]);
addedge(rt[i][j-],rt[i][j]);
}
if(isupper(s[i][j]))bg[s[i][j]-'A']=rt[i][j];
else if(islower(s[i][j]))ed[s[i][j]-'a']=rt[i][j];
}
for(int i=; i<tot; ++i)for(int j=; j<tot; ++j)for(int k=; k<tot; ++k)d[i][j][k]=-;
for(int i=; i<; ++i)bfs(ed[i],h[i]);
printf("%d\n",Astar());
}
return ;
}
A*
我用A*算法跑样例的速度明显快了好几个档次，但提交上去却依旧跑了400+ms，看来A*终究逃不过被卡的命运~~