紫书搜索例题7-9 UVA

题目链接:

题意:

题解:

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

代码:

双向bfs：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 1e5+10;
 17 
 18 int w, h, n, s[3], t[3];
 19 char dataset[20][20];
 20 int G[200][5], color[200][200][200], dis[200][200][200];
 21 int deg[200];
 22 
 23 int dx[] = {0,0,0,1,-1};
 24 int dy[] = {0,1,-1,0,0};
 25 
 26 int ID(int a,int b,int c){
 27     return (a<<16) | (b<<8) | c;
 28 }
 29 
 30 bool conflict(int a,int b,int a2,int b2){
 31     return a2==b2 || (a==b2 && b==a2);
 32 }
 33 
 34 int bfs(){
 35     queue<int> qf;
 36     queue<int> qb;
 37     dis[s[0]][s[1]][s[2]] = 0;
 38     dis[t[0]][t[1]][t[2]] = 1;
 39     qf.push(ID(s[0],s[1],s[2]));
 40     qb.push(ID(t[0],t[1],t[2]));
 41     color[s[0]][s[1]][s[2]] = 1;
 42     color[t[0]][t[1]][t[2]] = 2;
 43 
 44     while(!qf.empty() || !qb.empty()){
 45         int fnum = qf.size(), bnum = qb.size();  //一层一层的拓展。而不是一个点
 46         while(fnum--){ 
 47             int u = qf.front(); qf.pop();
 48             int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff; //解码出出列状态三个小鬼的位置
 49 
 50             for(int i=0; i<deg[a]; i++){
 51                 int a2 = G[a][i];
 52                 for(int j=0; j<deg[b]; j++){
 53                     int b2 = G[b][j];
 54                     if(conflict(a,b,a2,b2)) continue;
 55                     for(int k=0; k<deg[c]; k++){
 56                         int c2 = G[c][k];
 57                         if(conflict(a,c,a2,c2)) continue;
 58                         if(conflict(b,c,b2,c2)) continue;
 59 
 60                         // if(dis[a2][b2][c2] != -1) continue;  // 不能再这样判断是否访问过了，因为是双向
 61                         if(color[a2][b2][c2] == 0){
 62                             color[a2][b2][c2] = 1;
 63                             dis[a2][b2][c2] = dis[a][b][c]+1;
 64                             qf.push(ID(a2,b2,c2));
 65                         }else if(color[a2][b2][c2] == 2){
 66                             return dis[a][b][c] + dis[a2][b2][c2];  // 这就是为啥最开始的终点初始为1步；
 67                         }
 68                     }
 69                 }
 70             }
 71         }
 72 
 73         while(bnum--){
 74             int u = qb.front(); qb.pop();
 75             int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff;
 76 
 77             for(int i=0; i<deg[a]; i++){
 78                 int a2 = G[a][i];
 79                 for(int j=0; j<deg[b]; j++){
 80                     int b2 = G[b][j];
 81                     if(conflict(a,b,a2,b2)) continue;
 82                     for(int k=0; k<deg[c]; k++){
 83                         int c2 = G[c][k];
 84                         if(conflict(a,c,a2,c2)) continue;
 85                         if(conflict(b,c,b2,c2)) continue;
 86 
 87                         // if(dis[a2][b2][c2] != -1) continue; 
 88                         if(color[a2][b2][c2] == 0){
 89                             color[a2][b2][c2] = 2;
 90                             dis[a2][b2][c2] = dis[a][b][c] + 1;
 91                             qb.push(ID(a2,b2,c2));
 92                         }else if(color[a2][b2][c2] == 1){
 93                             return dis[a][b][c] + dis[a2][b2][c2];
 94                         }
 95                     }
 96                 }
 97             }
 98         }
 99     }
100 
101     return -1;
102 }
103 
104 int main(){
105     while(scanf("%d%d%d
",&w,&h,&n)==3 && (w+h+n)){
106         for(int i=0; i<h; i++) gets(dataset[i]);
107         int cnt=0,x[200],y[200],id[20][20];
108         for(int i=0; i<h; i++)
109             for(int j=0; j<w; j++){
110                 if(dataset[i][j]!='#'){
111                     x[cnt]=i,y[cnt]=j,id[i][j] = cnt;  // cnt表示有多少个空白块
112                     if(islower(dataset[i][j])) s[dataset[i][j]-'a'] = cnt;
113                     if(isupper(dataset[i][j])) t[dataset[i][j]-'A'] = cnt; 
114                     cnt++;
115                 }
116             }
117 
118         for(int i=0; i<cnt; i++){ // 用空白块建图
119             deg[i] = 0;  // i这个白块周围有多少的白块，就是连线嘛
120             for(int j=0; j<5; j++){
121                 int tx=x[i]+dx[j], ty=y[i]+dy[j];
122                 if(dataset[tx][ty] != '#') G[i][deg[i]++] = id[tx][ty];
123             }
124         }
125 
126         if(n <= 2) { deg[cnt]=1; G[cnt][0]=cnt; s[2]=t[2]=cnt; cnt++;}
127         if(n <= 1) { deg[cnt]=1; G[cnt][0]=cnt; s[1]=t[1]=cnt; cnt++;}
128 
129         memset(dis,-1,sizeof(dis));
130         memset(color,0,sizeof(color));
131 
132         printf("%d
",bfs());
133 
134     }
135 
136     return 0;
137 }

单向bfs：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 1e5+10;
 17 
 18 int w,h,n;
 19 int G[200][5],dis[200][200][200],deg[200],s[3],t[3];
 20 char dataset[20][20];
 21 int dx[] = {0,0,0,1,-1};
 22 int dy[] = {0,1,-1,0,0};
 23 
 24 inline int ID(int a,int b,int c){
 25     return (a<<16) | (b<<8) | c;
 26 }
 27 
 28 bool conflict(int a,int b,int a2,int b2){
 29     return (a2==b2) || (a==b2 && b==a2);
 30 }
 31 
 32 int bfs(){
 33     queue<int> q;
 34     q.push(ID(s[0],s[1],s[2]));
 35     dis[s[0]][s[1]][s[2]] = 0;
 36     while(!q.empty()){
 37         int u = q.front(); q.pop();
 38         int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u & 0xff;
 39         if(a==t[0] && b==t[1] && c==t[2]) return dis[a][b][c];
 40 
 41         for(int i=0; i<deg[a]; i++){
 42             int a2 = G[a][i];
 43             for(int j=0; j<deg[b]; j++){
 44                 int b2 = G[b][j];
 45                 if(conflict(a,b,a2,b2)) continue;
 46                 for(int k=0; k<deg[c]; k++){
 47                     int c2 = G[c][k];
 48                     if(conflict(a,c,a2,c2)) continue;
 49                     if(conflict(b,c,b2,c2)) continue;
 50 
 51                     if(dis[a2][b2][c2]!=-1) continue;
 52                     dis[a2][b2][c2] = dis[a][b][c] + 1;
 53                     q.push(ID(a2,b2,c2)); 
 54                 }
 55             }
 56         }
 57     }
 58     return -1;
 59 }
 60 
 61 int main(){
 62     while(~scanf("%d%d%d
",&w,&h,&n) && n){
 63         for(int i=0; i<h; i++) gets(dataset[i]);
 64 
 65         // for(int i = 0; i < h; i++)  fgets(dataset[i], 20, stdin);
 66 
 67         int cnt=0,x[200],y[200],id[20][20];
 68         for(int i=0; i<h; i++)
 69             for(int j=0; j<w; j++){
 70                 if(dataset[i][j] != '#'){
 71                     x[cnt]=i,y[cnt]=j,id[i][j]=cnt;
 72                     if(islower(dataset[i][j])) s[dataset[i][j]-'a'] = cnt;
 73                     else if(isupper(dataset[i][j])) t[dataset[i][j]-'A'] = cnt;
 74                     cnt++;
 75                 }
 76             }
 77 
 78         for(int i=0; i<cnt; i++){
 79             deg[i] = 0;
 80             for(int j=0; j<5; j++){
 81                 int tx=x[i]+dx[j], ty=y[i]+dy[j];
 82                 if(dataset[tx][ty]!='#') G[i][deg[i]++] = id[tx][ty];
 83             }
 84         }
 85         if(n<=2) { deg[cnt]=1; G[cnt][0]=cnt; s[2]=t[2]=cnt; cnt++;}
 86         if(n<=1) { deg[cnt]=1; G[cnt][0]=cnt; s[1]=t[1]=cnt; cnt++;}
 87 
 88         memset(dis,-1,sizeof(dis));
 89 
 90         printf("%d
",bfs());
 91     }
 92 
 93     return 0;
 94 }
 95 5 5 2
 96 #####
 97 #A#B#
 98 #   #
 99 #b#a#
100 #####
101 16 4 3
102 ################
103 ## ########## ##
104 #    ABCcba    #
105 ################
106 0 0 0

紫书搜索 例题7-9 UVA

题目链接:

题意:

题解:

代码:

紫书搜索例题7-9 UVA