首页 > 代码库 > UVa 1601 || POJ 3523 The Morning after Halloween (BFS || 双向BFS && 降维 && 状压)
UVa 1601 || POJ 3523 The Morning after Halloween (BFS || 双向BFS && 降维 && 状压)
题意 ：w*h（w,h≤16）网格上有n（n≤3）个小写字母（代表鬼）。要求把它们分别移动到对应的大写字母里。每步可以有多个鬼同时移动（均为往上下左右4个方向之一移动），但每步结束之后任何两个鬼不能占用同一个位置，也不能在一步之内交换位置。输入保证所有空格连通，所有障碍格也连通，且任何一个2*2子网格中至少有一个障碍格。输出最少的步数。输入保证有解。
分析 ：可以将当前所有小鬼的位置作为一个状态，然后模拟小鬼移动BFS拓展出其他可行状态并且顺带记录步数，直到所有的小鬼都到达终点。首先状态如何表示才能更方便去进行广搜？以前遇到的BFS大多都是一个起始一个终止，但是这里有多个小鬼，也就是多个起点多个终点，由于这里小鬼之间的位置会有互相影响的情况，所以自然不能分开来BFS找各自的最短路径再进行相加，广搜状态的定义直接影响到判重和状态拓展，对于判重，我们这里可能最多需要记录三个小鬼的位置状态，那如何进行判重呢？直接用结构体装起来再丢到set里面？直接开个高维度的vis数组？那空间复杂度肯定是爆炸的。既要保证时间又要保证空间，所以考虑降维操作，我们可以使用某种方法将二维的坐标映射成一个整数使用一个初始化全为-1的dis[][][]数组来表示三个小鬼的位置(即状态)，同样用这个来记录此状态下的步数，这样就可以顺利进行判重和状态转移了。||| 再者虽然时限给的很大，但是如果纯BFS搜的话根据小道消息还是会TLE，这里为了避免每一次进行状态拓展的时候频繁地进行判断出界和往四个方向搜，直接先预处理每一个点，看这个点能到达那些点，当有小鬼在这个点需要状态转移的时候就能直接找到可走区域，不用判来判去，这里的记录方法是使用类似邻接表的一种结构，开个数组Go[][]和一个长度数组deg[]，Go[i][deg[0]~deg[i]]表示 i 这个点的各个可行区，总共有deg[0]到deg[i]这么多(刚刚说过，已经对二维的坐标进行了降维操作，我们可以通过 i 找到原始的二维坐标，所以降维还给我们的可行区域预处理带来了很大的便利) ||| 还有就是刚刚上面的大体思路里面有个将二维的坐标进行映射变成一维的操作，直接使用数组row[]和col[]来保存二维坐标的行列，用变量cnt来保存坐标个数，也就是映射的函数值，每加一个就进行 row[cnt]=行, col[cnt]=列, cnt++;操作即可，不过还有一个问题，那如果有三个小鬼的话，装进队列的即使降维也是有三个整数，开个结构体也行，但是这里有一个更省空间的方法，就是采用二进制，比如进来三个小鬼的坐标a, b, c，根据我们刚刚映射的规则和w,h<=16，我们可以知道a,b,c<=16*16，用八位二进制就能表示出来，那就用一个24位的二进制来将这三个八位二进制保存起来，即(a<<16)|(b<<8)|c，就变成了一个整数，装进队列里面，取出来的时候就进行逆向分解就OK，即a = (queue.front()>>16)&0xff，b = (queue.front())>>8)&0xff, c = queue.front()&0xff。||| 细节就大概如此，为了更快可以进行双向BFS，即从终点和从起点分别搜，直到搜到双方都搜过的点，那权值相加就是答案了，可以参考=》 http://www.cppblog.com/Yuan/archive/2011/02/23/140553.aspx
单向BFS：
#include<bits/stdc++.h> using namespace std; int maxn = 260; int ROW, COl, Lnum; int cnt = 0; char G[20][20], blank[20][20]; int st[5], en[5]; int st_top = 0, en_top = 0; int Move[5][2] = { {1,0},{0,1},{-1,0},{0,-1},{0,0} }; int deg[260]; int Go[260][10]; int row[260]; int col[260]; int dis[260][260][260]; inline int Get_ID(int a, int b, int c)//->learn { return (a<<16)|(b<<8)|c; } inline bool check(int fir_st, int sec_st, int fir_en, int sec_en)//->learn { return fir_en==sec_en || (fir_en==sec_st && sec_en==fir_st); } inline int bfs() { int u = Get_ID(st[0], st[1], st[2]); memset(dis, -1, sizeof(dis)); dis[st[0]][st[1]][st[2]] = 0; queue<int> q; q.push(u); while(!q.empty()){ int top = q.front(); q.pop(); //int a = top>>16, b = top>>8, c = top; int a = (top>>16)&0xff, b = (top>>8)&0xff, c = top&0xff;//->Learn if(a==en[0] && b==en[1] && c==en[2]) return dis[a][b][c];//->Learn the dis for(int i=0; i<deg[a]; i++){ int a2 = Go[a][i]; for(int j=0; j<deg[b]; j++){ int b2 = Go[b][j]; if(check(a, b, a2, b2)) continue; for(int k=0; k<deg[c]; k++){ int c2 = Go[c][k]; if(check(a, c, a2, c2)) continue; if(check(b, c, b2, c2)) continue; if(dis[a2][b2][c2] != -1) continue;//->learn dis[a2][b2][c2] = dis[a][b][c] + 1;//这里实际上也是和每一个状态存一个权值是一样的，这里注意bfs找最短路时候的状态可以像dfs那样子走过不走 //但是这种状态式的就要想办法记录状态来避免重复情况 q.push(Get_ID(a2,b2,c2)); } } } } return -1; } int main(void) { while(~scanf("%d%d%d", &COl, &ROW, &Lnum) && (COl&&ROW&&Lnum)){ getchar(); cnt = 0;//caution for(int i=0; i<ROW; i++){ gets(G[i]); for(int j=0; j<COl; j++){ if(G[i][j]!=‘#‘){ blank[i][j] = cnt; row[cnt] = i, col[cnt] = j; if(islower(G[i][j])) st[G[i][j]-‘a‘] = cnt; else if(isupper(G[i][j])) en[G[i][j]-‘A‘] = cnt; cnt++; } } } //for(int i=0; i<cnt; i++) printf("%d %d\n", row[i], col[i]); for(int i=0; i<cnt; i++){ deg[i] = 0; for(int j=0; j<5; j++){ int y = row[i] + Move[j][0]; int x = col[i] + Move[j][1]; if(G[y][x]!=‘#‘ && (y>=0&&y<ROW) && (x>=0&&x<COl)){ Go[i][deg[i]++] = blank[y][x];//blank use } } } if(Lnum<=2){//->Learn have not influence deg[cnt] = 1; st[2] = en[2] = cnt; Go[cnt][0] = cnt++; } if(Lnum<=1){ deg[cnt] = 1; st[1] = en[1] = cnt; Go[cnt][0] = cnt++; } printf("%d\n", bfs()); } return 0; }
双向BFS(参考=》 http://blog.csdn.net/qq_34446253/article/details/51346622 但是我对其进行了步数的改动，保证是一层层解决)：
#include<cstdio> #include<cstring> #include<cctype> #include<queue> using namespace std; const int maxs=20; const int maxn=200; struct Seed{ int u, step; }; int s[3],t[3]; int deg[maxn],G[maxn][5]; //G[][]是邻接表保存，deg[i]保存第i个点有几个相连点 int dis[maxn][maxn][maxn],dis_back[maxn][maxn][maxn]; //判重同时也记录距离 int ID(int a,int b,int c) //三位数变为一位数记录 { return (a<<16)|(b<<8)|c; //0|1=1; } bool conflict(int a,int b,int a2,int b2) { return b2==a2||(a==b2&&b==a2); //不能穿过和重合 } int bfs(queue<Seed>& q,int d[maxn][maxn][maxn], int step) { while(1){ Seed Top = q.front(); if(Top.step!=step) break; q.pop(); int u = Top.u; int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff; if(dis[a][b][c]!=-1&&dis_back[a][b][c]!=-1) return dis[a][b][c]+dis_back[a][b][c]; // 当遇到正反搜索都搜过的节点就表明已经找到解了 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(d[a2][b2][c2] != -1) continue; d[a2][b2][c2] = d[a][b][c]+1; Seed temp; temp.step = step+1, temp.u=ID(a2,b2,c2); q.push(temp); } } } } return -1; } int solve() { Seed fir, fir_back; fir.step=0, fir.u=ID(s[0],s[1],s[2]); queue<Seed> q; q.push(fir); memset(dis,-1,sizeof(dis)); dis[s[0]][s[1]][s[2]]=0; queue<Seed> q_back; fir_back.step=0, fir_back.u=ID(t[0],t[1],t[2]); q_back.push(fir_back); //终点出发 memset(dis_back,-1,sizeof(dis_back)); dis_back[t[0]][t[1]][t[2]]=0; int step = 0; int ans; while(1) //正着搜一个节点，反着搜一个节点 { ans=bfs(q,dis,step); if(ans!=-1) return ans; ans=bfs(q_back,dis_back,step); if(ans!=-1) return ans; step++; } return -1; } int main() { int w,h,n; while(scanf("%d%d%d",&w,&h,&n)==3&&n) { getchar(); //读取一个回车 char maze[20][20]; for(int i=0;i<h;i++) fgets(maze[i],20,stdin); //比scanf("%c",&maze[i][j])方便或者用cin>>maze[i]但比较慢; int cnt=0,x[maxn],y[maxn],id[maxs][maxs]; for(int i=0;i<h;i++) for(int j=0;j<w;j++) { char ch=maze[i][j]; if(ch!=‘#‘) { x[cnt]=i;y[cnt]=j; //记录每个编号的横纵坐标，方便等下记录与其连接的节点 id[i][j]=cnt; //对每个非‘#‘节点编号，cnt表示编号 if(islower(ch)) s[ch-‘a‘]=cnt; else if(isupper(ch)) t[ch-‘A‘]=cnt; cnt++; } } const int dx[]={1,-1,0, 0,0}; //可以走五步 const int dy[]={0, 0,1,-1,0}; for(int i=0;i<cnt;i++) { deg[i]=0; for(int dir=0;dir<5;dir++) { int nx=x[i]+dx[dir]; int ny=y[i]+dy[dir]; if(maze[nx][ny]!=‘#‘) G[i][deg[i]++]=id[nx][ny]; //G[i][0~deg[i]-1]是保存从i点出发可到的点; } } if(n<=2) deg[cnt]=1,G[cnt][0]=cnt,s[2]=t[2]=cnt++; //对于不到3个的，新建一个点，起点终点在同一位置且该点只能到该点，即自环 if(n<=1) deg[cnt]=1,G[cnt][0]=cnt,s[1]=t[1]=cnt++; printf("%d\n",solve()); } return 0; }
刘汝佳源码：
// UVa1601 The Morning after Halloween // Rujia Liu // This code implements the simpliest yet efficient-enough algorithm I‘m aware of // Readers are encouraged to experiment on other algorithms (especially for better efficiency!) #include<cstdio> #include<cstring> #include<cctype> #include<queue> using namespace std; const int maxs = 20; const int maxn = 150; // 75% cells plus 2 fake nodes const int dx[]={1,-1,0,0,0}; // 4 moves, plus "no move" const int dy[]={0,0,1,-1,0}; inline int ID(int a, int b, int c) { return (a<<16)|(b<<8)|c; } int s[3], t[3]; // starting/ending position of each ghost int deg[maxn], G[maxn][5]; // target cells for each move (including "no move") inline bool conflict(int a, int b, int a2, int b2) { return a2 == b2 || (a2 == b && b2 == a); } int d[maxn][maxn][maxn]; // distance from starting state int bfs() { queue<int> q; memset(d, -1, sizeof(d)); q.push(ID(s[0], s[1], s[2])); // starting node d[s[0]][s[1]][s[2]] = 0; while(!q.empty()) { int u = q.front(); q.pop(); int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff; if(a == t[0] && b == t[1] && c == t[2]) return d[a][b][c]; // solution found 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(d[a2][b2][c2] != -1) continue; d[a2][b2][c2] = d[a][b][c]+1; q.push(ID(a2, b2, c2)); } } } } return -1; } int main() { int w, h, n; while(scanf("%d%d%d\n", &w, &h, &n) == 3 && n) { char maze[20][20]; for(int i = 0; i < h; i++) fgets(maze[i], 20, stdin); // extract empty cells int cnt, x[maxn], y[maxn], id[maxs][maxs]; // cnt is the number of empty cells cnt = 0; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) if(maze[i][j] != ‘#‘) { x[cnt] = i; y[cnt] = j; id[i][j] = cnt; if(islower(maze[i][j])) s[maze[i][j] - ‘a‘] = cnt; else if(isupper(maze[i][j])) t[maze[i][j] - ‘A‘] = cnt; cnt++; } // build a graph of empty cells for(int i = 0; i < cnt; i++) { deg[i] = 0; for(int dir = 0; dir < 5; dir++) { int nx = x[i]+dx[dir], ny = y[i]+dy[dir]; // "Outermost cells of a map are walls" means we don‘t need to check out-of-bound if(maze[nx][ny] != ‘#‘) G[i][deg[i]++] = id[nx][ny]; } } // add fakes nodes so that in each case we have 3 ghosts. this makes the code shorter if(n <= 2) { deg[cnt] = 1; G[cnt][0] = cnt; s[2] = t[2] = cnt++; } if(n <= 1) { deg[cnt] = 1; G[cnt][0] = cnt; s[1] = t[1] = cnt++; } printf("%d\n", bfs()); } return 0; }
UVa 1601 || POJ 3523 The Morning after Halloween (BFS || 双向BFS && 降维 && 状压)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。