给出一个最大为16×16的迷宫图和至多3个ghost的起始位置和目标位置，求最少经过几轮移动可以使三个ghost都到达目标位置。每轮移动中，每个ghost可以走一步，也可以原地不动，，需要注意的是任意两个ghost不能在相同的位置，因此也不能出现任意两个ghost对穿，也就是原来是ab，移动之后是ba。每个迷宫图’#’表示墙，’ ‘表示空地，小写字母表示ghost的起始位置，大写字母表示对应ghost的目标位置，比如’a’应该走到’A’。保证任意2×2的空间内都有一个’#’。
看起来就像是人数多了点的走迷宫嘛，BFS就是了。如果这么做的话果断就会超时，因为在每一个状态可以走的路太多，3个ghost的话，每个有5个方向可走，3个加起来除去原地不动还有124种走法，而且算出来的最少步数也不一定少，第三组样例的步数就多达77步，空间开不下，时间花得多。所以这道题就一定得优化了。
首先是尽量避免搜索不合法的走法。这个时候就是题里的一个细节，保证任意2×2空间内都有一个‘#’，也就是说，能走的124步里面有相当多的情况是不合法的。每次都压到队列里面然后不合法再排除就浪费了很多时间，所以这就是优化的入口。这里用的办法是把迷宫图给转换成了图，用邻接表保存起来，这样搜索的时候只走可以走的点，省去了走‘#’再排除的时间。
其次，在判重上也可以提高效率。一开始的时候我用了结构体储存ghost的位置，还动态调整ghost的数量，然后想办法用哈希判重，结果搞得效率奇慢无比样例都跑不出来。实际上还是根据任意2×2都有’#’这个细节，可以粗略的估计出整个迷宫中可以走的空地不超过200个，3个ghost的话建一个三维数组，200×200×200=8000000，完全开得下。另外考虑ghost数量不同的问题，这里想到的方法是把不存在的多余的ghost放到一个孤立的点中，然后使其起始位置和目标位置相同即可，这样就避免了需要根据情况动态调整的麻烦。
靠着上面两条，已经完全可以A过这题了。
嗯，那么思路就是获得“输入→建图→BFS”了。想法是很简单，写起来代码能力差真是个问题，各种卡各种崩各种不对，唉……
其实这只是部分的优化而已，如果还要提高效率的话，就需要用到双向BFS了。不过考虑到本渣的水平……先从单向的过度吧，接下来开始改双向。
#include <cstdio>#include <cstring>#include <cctype>#include <list>#include <algorithm>using namespace std;int w, h, n;char pic[20][20]; // 输入int num[20][20]; // 输入中的位置→图中节点的编号int vis[200][200][200]; // 标记数组int connect[200][200]; // 邻接表int all; // 图中节点的数量int que[10000000][4]; // BFS队列int goal[4]; // 目标状态inline void BFS() {// 初始化memset(vis, 0, sizeof(vis));int fro = 0, rear = 1;vis[que[0][1]][que[0][2]][que[0][3]] = true;while(fro < rear) {int &step = que[fro][0], &a = que[fro][1], &b = que[fro][2], &c = que[fro][3];if(a == goal[1] && b == goal[2] && c == goal[3]) { goal[0] = step; return; }for(int i = 0, t1; i <= connect[a][0]; ++i) {t1 = (i == 0 ? a : connect[a][i]);for(int j = 0, t2; j <= connect[b][0]; ++j) {t2 = (j == 0 ? b : connect[b][j]);for(int k = 0, t3; k <= connect[c][0]; ++k) {t3 = (k == 0 ? c : connect[c][k]);// 判断冲突—–if((t1 && t2 && t1 == t2) || (t1 && t3 && t1 == t3) || (t2 && t3 && t2 == t3)) continue; // 不能重合if(t1 && t2 && t1 == b && t2 == a) continue; // t1,t2不能对穿if(t1 && t3 && t1 == c && t3 == a) continue; // t1,t3不能对穿if(t2 && t3 && t2 == c && t3 == b) continue; // t2,t3不能对穿// ———-if(!vis[t1][t2][t3]) {vis[t1][t2][t3] = 1;que[rear][0] = step + 1, que[rear][1] = t1, que[rear][2] = t2, que[rear][3] = t3;++rear;}}}}++fro;}}int main() {int _t = 0;while(scanf("%d%d%d", &w, &h, &n) && w && h && n) {// 读取输入—–gets(pic[0]);for(int i = 0; i != h; ++i) gets(pic[i]);// ———-// 根据输入建立图—–// 初始化memset(connect, 0, sizeof(connect));all = 0;// 获得编号for(int i = 0; i != h; ++i) for(int j = 0; j != w; ++j) {if(pic[i][j] != '#') num[i][j] = ++all;else num[i][j] = 0;}// 建立图for(int i = 0; i != h; ++i) for(int j = 0; j != w; ++j) if(num[i][j]) {int &pos = num[i][j];if(num[i + 1][j]) connect[pos][++connect[pos][0]] = num[i + 1][j];if(num[i – 1][j]) connect[pos][++connect[pos][0]] = num[i – 1][j];if(num[i][j + 1]) connect[pos][++connect[pos][0]] = num[i][j + 1];if(num[i][j – 1]) connect[pos][++connect[pos][0]] = num[i][j – 1];}// ———-// 寻找初始状态和目标状态（测了一下字母范围只在abc之间所以偷懒就这么写了）//初始化que[0][0] = que[0][1] = que[0][2] = que[0][3] = 0;goal[0] = goal[1] = goal[2] = goal[3] = 0;// 寻找初始状态for(int i = 0; i != h; ++i) for(int j = 0; j != w; ++j) if(islower(pic[i][j])) {if(pic[i][j] == 'a') que[0][1] = num[i][j];if(pic[i][j] == 'b') que[0][2] = num[i][j];if(pic[i][j] == 'c') que[0][3] = num[i][j];}// 寻找目标状态for(int i = 0; i != h; ++i) for(int j = 0; j != w; ++j) if(isupper(pic[i][j])) {if(pic[i][j] == 'A') goal[1] = num[i][j];if(pic[i][j] == 'B') goal[2] = num[i][j];if(pic[i][j] == 'C') goal[3] = num[i][j];}// ———-BFS();printf("%d\n", goal[0]);}}
那什么是双向BFS呢？就是从两个方向进行搜索嘛，一边从起点开始向终点搜索，一边从终点倒着向前搜索，然后从两头往中间接。在算法中的实现方法是正反两方向的搜索交替进行，当搜索出相同的状态时，路就打通了，步数就是两边BFS步数的和。
一定要成为你工作最大的资产。
