【题目链接】点击打开链接

【题意】w*h（w,h <= 16）网格中有n（n<=3）个小写字母（代表鬼），要求把它们分别移动到对应的大写字母里。每一步可以有多个鬼移动（均为往上下左右4个方向之1移动），但每一步结束之后，任何两个鬼不能占用同一个位置，也不能在一步之内交换位置。

【解题方法】方法是把所有可以移动的格子找出来建立一张图，就是把障碍物给删除，统计每个可以空格或者有鬼的格子可以移动到哪些格子，这样在判断的时候就节省了许多时间。然后bfs找最短路。具体可以看紫书206页，书上还提到了可以用双向BFS的方法，现在不会。


【AC代码】


//
//Created by BLUEBUFF 2016/1/9
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 20;
const int maxm = 300;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const double PI = acos(-1);
//head

int getnum(int a, int b, int c){ //编码
    return (a << 16) | (b << 8) | c;
}

int ok(int a, int b, int a1, int b1){ //两种非法的情况
    return ((a1 == b1) || (a1 == b && b1 == a));
}

int dir[5][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}, {0, 0}};
int id[maxn][maxn], G[maxm][5]; //由于相邻节点最多5个,包含自身
int st[3], en[3]; //st存放起始位置，en存放结束位置
int edge[maxm], d[maxm][maxm][maxm];//edge数组存放第i个结点具有的相邻结点数目
int w, h, n, cnt;
char M[maxn][maxn]; //原地图
void bfs()
{
    queue <int> q;
    memset(d, -1, sizeof(d));
    q.push(getnum(st[0], st[1], st[2]));
    d[st[0]][st[1]][st[2]] = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        int a = (u >> 16) & 255, b = (u >> 8) & 255, c = u & 255; //解码各个鬼的位置
        if(a == en[0] && b == en[1] && c == en[2]) return; //找个目标状态
        for(int i = 1; i <= edge[a]; i++){
            int a1 = G[a][i];
            for(int j = 1; j <= edge[b]; j++){
                int b1 = G[b][j];
                if(ok(a, b, a1, b1)) continue;
                for(int k = 1; k <= edge[c]; k++){
                    int c1 = G[c][k];
                    if(ok(a, c, a1, c1)) continue;
                    if(ok(b, c, b1, c1)) continue;
                    if(d[a1][b1][c1] == -1){
                        d[a1][b1][c1] = d[a][b][c] + 1;
                        q.push(getnum(a1, b1, c1));
                    }
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d%d", &w, &h, &n) != EOF && n)
    {
        char c = getchar();
        while(c != '\n') c = getchar();
        REP2(i, 1, h){
            fgets(M[i] + 1, 20, stdin);
        }
        cnt = 0;
        int x[maxm], y[maxm];
        REP2(i, 1, h){
            REP2(j, 1, w){
                if(M[i][j] != '#'){
                    id[i][j] = ++cnt;//利用矩阵存稀疏图，cnt是每个结点的序号，也代表了最终的结点数
                    x[cnt] = i;
                    y[cnt] = j;
                    if('a' <= M[i][j] && M[i][j] <= 'c'){
                        st[M[i][j] - 'a'] = cnt; //找每一个鬼
                    }
                    if('A' <= M[i][j] && M[i][j] <= 'C'){
                        en[M[i][j] - 'A'] = cnt; //找目标位置
                    }
                }
            }
        }
        REP2(i, 1, cnt){
            edge[i] = 0;
            REP1(j, 0, 5){
                int dx = x[i] + dir[j][0];
                int dy = y[i] + dir[j][1];
                if(M[dx][dy] != '#'){
                    G[i][++edge[i]] = id[dx][dy];//寻找每个结点的相邻结点，包括自己
                }
            }
        }
        if(n <= 2){
            edge[++cnt] = 1;
            G[cnt][1] = cnt;
            st[2] = en[2] = cnt;
        }
        if(n <= 1){
            edge[++cnt] = 1;
            G[cnt][1] = cnt;
            st[1] = en[1] = cnt;
        }
        bfs();
        printf("%d\n", d[en[0]][en[1]][en[2]]);
    }
    return 0;
}