紫书搜索例题7-9 UVA - 1601 The Morning after Halloween双向bfs

xiaoxiao2021-03-25 55

题目链接:

https://vjudge.net/problem/UVA-1601

题意:

题解:

http://blog.csdn.net/qq_29169749/article/details/51420097 隐式图搜索问题，类似dijkstra，用bfs解决，这个是单向搜索，弊端是有时候随着搜索的深入，可扩展的结点会越来越多，造成效率变慢，用双向bfs可以解决这个问题

代码:

双向bfs：

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } // const int maxn = 1e5+10; int w, h, n, s[3], t[3]; char dataset[20][20]; int G[200][5], color[200][200][200], dis[200][200][200]; int deg[200]; int dx[] = {0,0,0,1,-1}; int dy[] = {0,1,-1,0,0}; int ID(int a,int b,int c){ return (a<<16) | (b<<8) | c; } bool conflict(int a,int b,int a2,int b2){ return a2==b2 || (a==b2 && b==a2); } int bfs(){ queue<int> qf; queue<int> qb; dis[s[0]][s[1]][s[2]] = 0; dis[t[0]][t[1]][t[2]] = 1; qf.push(ID(s[0],s[1],s[2])); qb.push(ID(t[0],t[1],t[2])); color[s[0]][s[1]][s[2]] = 1; color[t[0]][t[1]][t[2]] = 2; while(!qf.empty() || !qb.empty()){ int fnum = qf.size(), bnum = qb.size(); //一层一层的拓展。而不是一个点 while(fnum--){ int u = qf.front(); qf.pop(); int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff; //解码出出列状态三个小鬼的位置 for(int i=0; i<deg[a]; i++){ int a2 = G[a][i]; for(int j=0; j<deg[b]; j++){ int b2 = G[b][j]; if(conflict(a,b,a2,b2)) continue; for(int k=0; k<deg[c]; k++){ int c2 = G[c][k]; if(conflict(a,c,a2,c2)) continue; if(conflict(b,c,b2,c2)) continue; // if(dis[a2][b2][c2] != -1) continue; // 不能再这样判断是否访问过了，因为是双向 if(color[a2][b2][c2] == 0){ color[a2][b2][c2] = 1; dis[a2][b2][c2] = dis[a][b][c]+1; qf.push(ID(a2,b2,c2)); }else if(color[a2][b2][c2] == 2){ return dis[a][b][c] + dis[a2][b2][c2]; // 这就是为啥最开始的终点初始为1步； } } } } } while(bnum--){ int u = qb.front(); qb.pop(); int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff; for(int i=0; i<deg[a]; i++){ int a2 = G[a][i]; for(int j=0; j<deg[b]; j++){ int b2 = G[b][j]; if(conflict(a,b,a2,b2)) continue; for(int k=0; k<deg[c]; k++){ int c2 = G[c][k]; if(conflict(a,c,a2,c2)) continue; if(conflict(b,c,b2,c2)) continue; // if(dis[a2][b2][c2] != -1) continue; if(color[a2][b2][c2] == 0){ color[a2][b2][c2] = 2; dis[a2][b2][c2] = dis[a][b][c] + 1; qb.push(ID(a2,b2,c2)); }else if(color[a2][b2][c2] == 1){ return dis[a][b][c] + dis[a2][b2][c2]; } } } } } } return -1; } int main(){ while(scanf("%d%d%d\n",&w,&h,&n)==3 && (w+h+n)){ for(int i=0; i<h; i++) gets(dataset[i]); int cnt=0,x[200],y[200],id[20][20]; for(int i=0; i<h; i++) for(int j=0; j<w; j++){ if(dataset[i][j]!='#'){ x[cnt]=i,y[cnt]=j,id[i][j] = cnt; // cnt表示有多少个空白块 if(islower(dataset[i][j])) s[dataset[i][j]-'a'] = cnt; if(isupper(dataset[i][j])) t[dataset[i][j]-'A'] = cnt; cnt++; } } for(int i=0; i<cnt; i++){ // 用空白块建图 deg[i] = 0; // i这个白块周围有多少的白块，就是连线嘛 for(int j=0; j<5; j++){ int tx=x[i]+dx[j], ty=y[i]+dy[j]; if(dataset[tx][ty] != '#') G[i][deg[i]++] = id[tx][ty]; } } if(n <= 2) { deg[cnt]=1; G[cnt][0]=cnt; s[2]=t[2]=cnt; cnt++;} if(n <= 1) { deg[cnt]=1; G[cnt][0]=cnt; s[1]=t[1]=cnt; cnt++;} memset(dis,-1,sizeof(dis)); memset(color,0,sizeof(color)); printf("%d\n",bfs()); } return 0; }

单向bfs：

转载请注明原文地址: https://ju.6miu.com/read-35103.html

技术

最新回复(0)

紫书搜索 例题7-9 UVA - 1601 The Morning after Halloween双向bfs

题目链接:

题意:

题解:

代码:

技术

紫书搜索例题7-9 UVA - 1601 The Morning after Halloween双向bfs