基本思路是BFS：

　　1. 题目中已经说了，每相连的2X2格子中必有一个‘#’,也就是，每个点周围最多也就三个方向可以走。因此，可以把所有空格都提出来，形成一个图，直接遍历每条边，而不是每次判断4个方向是否可以走

　　2.关于结点判重，最初的想法是想用一个六维数组，后来参考了其它，发现其实可以用一个三维数字代替，每个点可以用数字代替，因为题目中整个图最多为16X16，所以数字最大为16*16 = 256，这样做的另一个好处是，移动字母也方便了，可以用数字代替点，比如从（0， 0）移动到（0，1）可以考做是从 0 移动到 1

　　3.N的数量不一，移动时要不要判断是N是多少？这是我刚开始的想法，个人采用递归的方法，先放一个点，再放下一个点，观察这是不是最后一个要移动的点，相对而言，比对每个N值进行单独处理要简单点。

 

注意点：题目输入的W，H，N中W是指宽度，即列数，而H即为行数。

 

收获及感悟：刚开始看到这题的时候已经吓着了，首先就是如何保存三个点状态，真的差点用六维数组或map了。在这里也学了一招，用整数依次标记每个点。另外，关于题意，刚开始理解不透，还在想a，b，c三者的先后移动顺序，后来发现想多了，任意顺序移动，判断移动后的状态是否可行即可。这题是在看了别人代码后才A掉的，非常感谢发布题解的同学。

 

参考资料：

　　1.

　　2.《算法竞赛入门经典（第2版）》

#include 
     
      using namespace std;const int MAXN = 16 + 5;char plan[MAXN][MAXN];int W, H, N;vector
      
        link[MAXN*MAXN];bool vis[MAXN*MAXN][MAXN*MAXN][MAXN*MAXN];int dir[4][2] = {0,1, 0,-1, 1,0, -1,0};struct State{    int ghostPos[5], step;};State finalState, firstState;// more than one ghost occupy a same position// p is the prev state, whether two ghots in s exchange with their positionbool isCollisionOrExChange(State& s, State& p) {    for(int i=0; i
       
        & q, State& former) {    for(size_t i=0; i
        
          q;    firstState.step = 0;    q.push(firstState);    SetVis(firstState, true);    while(!q.empty()) {        State t = q.front();        q.pop();        // Test(t);        if(IsFinal(t)) {            return t.step;        }        State newS;        newS.step = t.step + 1;        NextState(newS, 0, q, t);    }    return -1;}// Make a Graphvoid MakeLink() {    for(int i=0; i
         
          =0 && x
          
           =0 && y
           
            > W >> H >> N) { if(!W && !H && !N) { break; } Work(); } return 0;}