紫书章七例题九 The Moring agter Halloween UVA1601(bfs,重新建图)
题意：给你一个图，然后小写字母同时去找大写字母。然后可以不动，上下左右移动（5种移动方式）。其中小写字母不能占用同一个位子，也不能在一步之内交换位子。
强行暴力会超时，但是，你强行暴力的时候，标记数组怎么标记？
所以这里采用的是将每一个可行的位子记录下来，建一个新图。
#include int aa=G[t1.a][i];for(int j=0;jint bb=G[t1.b][j];if(judge(t1.a,t1.b,aa,bb)) continue;for(int k=0;kint cc=G[t1.c][k];if(judge(t1.a,t1.c,aa,cc)) continue;if(judge(t1.b,t1.c,bb,cc)) continue;if(d[aa][bb][cc]!=-1) continue;d[aa][bb][cc]=d[t1.a][t1.b][t1.c]+1;q.push((node){aa,bb,cc});}}}}
}
int main()
{int w,h,n;while(scanf("%d %d %d",&w,&h,&n)!=EOF&&n){char M[20][20];int x[400],y[400];int cnt=0,id[20][20];memset(dg,0,sizeof(dg));memset(G,0,sizeof(G));memset(id,0,sizeof(id));getchar();for(int i=0;i20,stdin);for(int j=0;jif(M[i][j]!='#'){y[cnt]=i,x[cnt]=j,id[i][j]=cnt;//id记录图中可行位子的编号，以便后面的新图if(islower(M[i][j])) s[M[i][j]-'a']=cnt;else if(isupper(M[i][j])) t[M[i][j]-'A']=cnt;cnt++;}}}for(int i=0;ifor(int j=0;j<5;j++){int xx=x[i]+nx[j];int yy=y[i]+ny[j];if(M[yy][xx]!='#'){G[i][dg[i]++]=id[yy][xx];//存图}}}//如果没有三个，就填充为3个，方便同一处理if(n<=1){s[1]=cnt,t[1]=cnt,G[cnt][0]=cnt,dg[cnt]=1;cnt++;}if(n<=2){s[2]=cnt,t[2]=cnt,G[cnt][0]=cnt,dg[cnt]=1;cnt++;}bfs();}return 0;
} 双向bfs，还是基于第一种方法。然后建好新图之后，因为我们知道起点和终点。然后我们就可以起点和终点同时走，然后相遇了，时间之和即为所求。相当于正着走一步，反走再走一步。然后一定要注意那个pop，要在之后用，因为有可能为下一步了，还没判断，就出去了。。。
#include int aa=G[t1.a][i];for(int j=0;jint bb=G[t1.b][j];if(judge(t1.a,t1.b,aa,bb)) continue;for(int k=0;kint cc=G[t1.c][k];if(judge(t1.a,t1.c,aa,cc)) continue;if(judge(t1.b,t1.c,bb,cc)) continue;if(d1[aa][bb][cc]==-1){d1[aa][bb][cc]=d1[t1.a][t1.b][t1.c]+1;q1.push((node){aa,bb,cc});}}}}q1.pop();}return 0;
}
int bfs2()
{node u=q2.front();int ans=d2[u.a][u.b][u.c];while(!q2.empty()){node t1=q2.front();if(ans!=d2[t1.a][t1.b][t1.c]) return 0;if(d1[t1.a][t1.b][t1.c]!=-1) return 1;for(int i=0;iint aa=G[t1.a][i];for(int j=0;jint bb=G[t1.b][j];if(judge(t1.a,t1.b,aa,bb)) continue;for(int k=0;kint cc=G[t1.c][k];if(judge(t1.a,t1.c,aa,cc)) continue;if(judge(t1.b,t1.c,bb,cc)) continue;if(d2[aa][bb][cc]==-1) {d2[aa][bb][cc]=d2[t1.a][t1.b][t1.c]+1;q2.push((node){aa,bb,cc});}}}}q2.pop();//注意这个是在后面}return 0;
}
int BFS()
{while(!q1.empty())q1.pop();while(!q2.empty())q2.pop();q1.push((node){s[0],s[1],s[2]});q2.push((node){t[0],t[1],t[2]});int ok=0,step=0;memset(d1,-1,sizeof(d1));memset(d2,-1,sizeof(d2));d1[s[0]][s[1]][s[2]]=0;d2[t[0]][t[1]][t[2]]=0;while(!q1.empty()&&!q2.empty()){if(bfs1()){ok=1;break;}elsestep++;if(bfs2()){ok=1;break;}else step++;}return step;
}int main()
{int w,h,n;while(scanf("%d %d %d",&w,&h,&n)!=EOF&&n){char M[20][20];int x[400],y[400];int cnt=0,id[20][20];memset(dg,0,sizeof(dg));memset(G,0,sizeof(G));memset(id,0,sizeof(id));memset(t,0,sizeof(t));memset(s,0,sizeof(s));getchar();for(int i=0;i20,stdin);for(int j=0;jif(M[i][j]!='#'){y[cnt]=i,x[cnt]=j,id[i][j]=cnt;//id记录图中可行位子的编号，以便后面的新图if(islower(M[i][j])) s[M[i][j]-'a']=cnt;else if(isupper(M[i][j])) t[M[i][j]-'A']=cnt;cnt++;}}}for(int i=0;ifor(int j=0;j<5;j++){int xx=x[i]+nx[j];int yy=y[i]+ny[j];if(M[yy][xx]!='#'){G[i][dg[i]++]=id[yy][xx];//存图}}}//如果没有三个，就填充为3个，方便同一处理if(n<=1){s[1]=cnt,t[1]=cnt,G[cnt][0]=cnt,dg[cnt]=1;cnt++;}if(n<=2){s[2]=cnt,t[2]=cnt,G[cnt][0]=cnt,dg[cnt]=1;cnt++;}printf("%d\n",BFS());}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！