UVa 1601 万圣节后的早晨

题意：

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

#include <bits/stdc++.h>
using namespace std;
const int maxw= 20, maxh = 20, maxn = 200;
int dir[5][2] = {{0,1}, {-1,0}, {0,-1}, {1,0}, {0, 0} };//сробвСио
int w, h, N;

int st[3],ed[3];

int D[maxn][maxn][maxn];

char maze[maxh][maxw];
int id[maxh][maxw];
int deg[maxn], G[maxn][5];

inline int ID(int a, int b, int c) { //将3个鬼的状态映射为一个int数
  return (a<<16)|(b<<8)|c;
}

inline bool conflict(int a, int b, int a2, int b2) { //处理冲突
  return a2 == b2 || (a2 == b && b2 == a);
}

int bfs(){
    queue<int> q;
    memset(D, -1, sizeof(D));
    q.push(ID(st[0],st[1],st[2]));
    D[st[0]][st[1]][st[2]] = 0; //记录这种状态所需步数
    while(!q.empty()){
        int u = q.front();
        int a = (u>>16) & 0xff, b = (u>>8) & 0xff, c = u & 0xff; //将数字还原为3个状态，每次只要int的后八位
        if(a == ed[0] && b == ed[1] && c == ed[2])
            return D[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(b,c,b2,c2)) continue;
                    if(conflict(a,c,a2,c2)) continue;
                    if(D[a2][b2][c2] == -1){
                        q.push(ID(a2,b2,c2));
                        D[a2][b2][c2] = D[a][b][c] + 1;
                    }
                }
            }
        }
        q.pop();
    }
    return -1;
}

int main()
{
    while(~scanf("%d %d %d
", &w,&h,&N) && N)
    {
        int cnt = 0, x[maxn], y[maxn];

        for(int i = 0; i < h; i++)
            fgets(maze[i], 20, stdin);


        for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++){
            if(maze[i][j] != '#'){
                id[i][j] = cnt;
                x[cnt] = i;y[cnt] = j; //给每个点（x,y）编号
                if(islower(maze[i][j])){
                    st[maze[i][j] - 'a'] = cnt;
                }
                if(isupper(maze[i][j])){
                    ed[maze[i][j] - 'A'] = cnt;
                }
                cnt++;
            }
        }

        for(int i = 0; i < cnt; i++){
            deg[i] = 0;
            for(int d = 0; d < 5; d++){
                int tx = x[i] + dir[d][0], ty = y[i] + dir[d][1];
                if(tx < 0 || tx >= h || ty < 0 || ty >= w || maze[tx][ty] == '#')
                    continue;
                G[i][deg[i]++] = id[tx][ty];//记录每个点可以走的点
            }
        }


        if(N <= 2) { deg[cnt] = 1; G[cnt][0] = cnt; st[2] = ed[2] = cnt++; } 
        if(N <= 1) { deg[cnt] = 1; G[cnt][0] = cnt; st[1] = ed[1] = cnt++; }
        printf("%d
", bfs());

    }
    return 0;
}