首页 > 代码库 > UVa1601 The Morning after Halloween (双向广度优先搜索)
UVa1601 The Morning after Halloween (双向广度优先搜索)
链接：http://acm.hust.edu.cn/vjudge/problem/51163
分析：已知起点和终点可以利用双向广度优先搜索，正向扩展一层，反向扩展一层，为防止退化，优先扩展结点数多的方向。因为障碍物很多防止TLE，可以先把图除了‘#’抠下来，用cnt给位置编号，x[cnt],y[cnt]为编号为cnt的格子的横纵坐标，id记录坐标为x,y格子的编号，然后找这些格子周围能走的格子，用deg[cnt]保存编号为cnt的格子周围能走的格子数，用G[cnt][i]保存编号为cnt的格子周围能走的第i个格子的编号，如果鬼的数量不足3，可以通过增加虚拟的格子，凑3个鬼，用来凑的鬼放在这个虚拟的格子里，并且设起点终点都是这个虚拟格子，且移动的方式只能原地不动。最后两个方向相遇两个d相加即求出最短路。
1 #include <cstdio> 2 #include <cctype> 3 #include <queue> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 150; 8 const int maxs = 20; 9 int w, h, n, deg[maxn], G[maxn][5], s[3], t[3];10 char maze[20][20];11 int d[maxn][maxn][maxn];12 int d2[maxn][maxn][maxn];13 14 inline int ID(const int& a, const int& b, const int& c) {15 return (a << 16) | (b << 8) | c;16 }17 18 inline bool conflict(const int& a, const int& b, const int& a2, const int& b2) {19 return a2 == b2 || (a2 == b && b2 == a);20 }21 22 int DBfs() {23 queue<int> q;24 queue<int> q2;25 queue<int> nxt;26 memset(d, -1, sizeof(d));27 memset(d2, -1, sizeof(d2));28 q.push(ID(s[0], s[1], s[2]));29 q2.push(ID(t[0], t[1], t[2]));30 d[s[0]][s[1]][s[2]] = 0;31 d2[t[0]][t[1]][t[2]] = 0;32 while (!q.empty() && !q2.empty()) {33 if (q.size() > q2.size()) swap(q, q2), swap(d, d2);34 for (int ii = 0, sz = q.size(); ii < sz; ii++) {35 int u = q.front(); q.pop();36 int a = (u >> 16) & 0xff; int b = (u >> 8) & 0xff; int c = u & 0xff;37 for (int i = 0; i < deg[a]; i++) {38 int a2 = G[a][i];39 for (int j = 0; j < deg[b]; j++) {40 int b2 = G[b][j];41 if (conflict(a, b, a2, b2)) continue;42 for (int k = 0; k < deg[c]; k++) {43 int c2 = G[c][k];44 if (conflict(a, c, a2, c2)) continue;45 if (conflict(b, c, b2, c2)) continue;46 if (d[a2][b2][c2] != -1) continue;47 d[a2][b2][c2] = d[a][b][c] + 1;48 if (d2[a2][b2][c2] >= 0) return d[a2][b2][c2] + d2[a2][b2][c2];49 nxt.push(ID(a2, b2, c2));50 }51 }52 }53 }54 swap(q, nxt);55 }56 return -1;57 }58 59 const int dx[5] = {1, -1, 0, 0, 0};60 const int dy[5] = {0, 0, 1, -1, 0};61 void init() {62 int cnt = 0, x[maxn], y[maxn], id[maxs][maxs]; 63 for (int i = 0; i < h; i++)64 for (int j = 0; j < w; j++)65 if (maze[i][j] != ‘#‘) {66 x[cnt] = i; y[cnt] = j; id[i][j] = cnt;67 if (islower(maze[i][j])) s[maze[i][j] - ‘a‘] = cnt;68 else if (isupper(maze[i][j])) t[maze[i][j] - ‘A‘] = cnt;69 cnt++;70 }71 for (int i = 0; i < cnt; i++) {72 deg[i] = 0;73 for (int dir = 0; dir < 5; dir++) {74 int nx = x[i] + dx[dir], ny = y[i] + dy[dir];75 if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;76 if (maze[nx][ny] != ‘#‘) G[i][deg[i]++] = id[nx][ny];77 }78 }79 if (n <= 1) { deg[cnt] = 1; G[cnt][0] = cnt; s[1] = t[1] = cnt++; }80 if (n <= 2) { deg[cnt] = 1; G[cnt][0] = cnt; s[2] = t[2] = cnt++; }81 }82 83 int main() {84 while (scanf("%d%d%d\n", &w, &h, &n) == 3 && n) {85 for (int i = 0; i < h; i++)86 fgets(maze[i], 20, stdin);87 init();88 printf("%d\n", DBfs());89 }90 return 0;91 }
UVa1601 The Morning after Halloween (双向广度优先搜索)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。