UVA - 1601 The Morning after Halloween (BFS/双向BFS/A*)

题目链接

挺有意思但是代码巨恶心的一道最短路搜索题。

因为图中的结点太多,应当首先考虑把隐式图转化成显式图,即对地图中可以相互连通的点之间连边,建立一个新图(由于每步不需要每个鬼都移动,所以每个点需要向自己也连一条边)。设d[i][j][k]为走到“A在结点i,B在结点j,C在结点k”的状态需要多少步,直接bfs即可。

注意由于鬼的个数不确定,为了减少特判,需要留出三个虚节点,把多出来的鬼的起点和终点都设到同一个虚节点上。

UVA - 1601 The Morning after Halloween (BFS/双向BFS/A*)
 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值相加即为最短距离。

UVA - 1601 The Morning after Halloween (BFS/双向BFS/A*)
 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值最小的结点进行扩展即可。

UVA - 1601 The Morning after Halloween (BFS/双向BFS/A*)
 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*终究逃不过被卡的命运~~

上一篇:c# – ServiceStack完成noob教程


下一篇:使用cavan标签+rangeSlider滑块插件动态调整扇形区域