解题思路：
1.注意到2*2方格中必有一个＃，那么最多只有192条通道，可以将所有非‘＃’的位置提取出来用邻接表的方式建图，通过bfs搜索目标位置。
2.将三个ghost的位置（a,b,c）作为状态量存储，如果采用邻接矩阵方式存储图，那么转移代价为5*5*5，很容易超时。分析题意可以知道图中结点大部分不是4个方向都能通过，用邻接表可以避免做多余的判断。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxv=; int di[]={,-,,,};
int dj[]={,,,-,}; int vis[maxv+][maxv+][maxv+];
typedef struct {
int p[]={};
int dist=;
}state; vector<int> G[maxv+];
char buff[][];
int id[][]; int w,h,n,vn,ans;
int ghost_ascii[];
state ghost_init_pos,ghost_target_pos; int read(){
memset(vis, , sizeof vis);
memset(ghost_ascii, , sizeof ghost_ascii);
memset(id, , sizeof id);
memset(buff, , sizeof buff);
memset(ghost_init_pos.p, , sizeof ghost_init_pos.p);
memset(ghost_target_pos.p, , sizeof ghost_target_pos.p);
scanf("%d%d%d",&w,&h,&n);
if(w==) return ; fgets(buff[], , stdin); for(int i=;i<h;i++)
fgets(buff[i], , stdin); vn=;
for(int i=;i<h;i++)
for(int j=;j<w;j++)
if(buff[i][j]!='#'){
vn++;
id[i][j]=vn;
}
char ch;
for(int i=;i<h;i++){
for(int j=;j<w;j++){
ch=buff[i][j]; if(ch!='#'){
int cur=id[i][j]; for(int pos=;pos<;pos++){
int x=i+di[pos],y=j+dj[pos];
if(x>=&&x<h&&y>=&&y<w&&id[x][y]){
int pre=id[x][y];
G[cur].push_back(pre);
}
} if(islower(ch)){
for(int k=;k<n;k++)
if(!ghost_ascii[k]||ghost_ascii[k]==ch){
ghost_ascii[k]=ch;
ghost_init_pos.p[k]=cur;
break;
}
}
else if(isupper(ch)){
for(int k=;k<n;k++){
if(!ghost_ascii[k]||ghost_ascii[k]==ch+'a'-'A'){
ghost_ascii[k]=ch+'a'-'A';
ghost_target_pos.p[k]=cur;
break;
}
}
}
}
}
}
return ;
}
bool check(const state& u,const state& u2){ for(int i=;i<n;i++)
for(int j=i+;j<n;j++)
if(u2.p[i]==u2.p[j]) return false; for(int i=;i<n;i++)
for(int j=i+;j<n;j++)
if(u2.p[i]==u.p[j]&&u2.p[j]==u.p[i]) return false;
return true;
}
void update(queue<state>& q,const state& u,int i,int j=,int k=){
state u2;
u2.p[]=G[u.p[]][i];
if(n>=) u2.p[]=G[u.p[]][j];
if(n==) u2.p[]=G[u.p[]][k];
if(!vis[u2.p[]][u2.p[]][u2.p[]]&&check(u, u2)) {
vis[u2.p[]][u2.p[]][u2.p[]]=;
u2.dist=u.dist+;
q.push(u2);
/*
for(int m=0;m<n;m++)
cout<<u.p[m]<<" ";
cout<<" to ";
for(int m=0;m<n;m++)
cout<<u2.p[m]<<" ";
cout<<u2.dist<<endl;
*/
}
}
void solve(){
queue<state> q;
q.push(ghost_init_pos);
vis[ghost_init_pos.p[]][ghost_init_pos.p[]][ghost_init_pos.p[]]=;
while(!q.empty()){
state u=q.front();q.pop(); if(memcmp(u.p,ghost_target_pos.p,sizeof ghost_target_pos.p)==) {
ans=u.dist;
break;
}
for(int i=;i<G[u.p[]].size();i++){
if(n==){
update(q, u, i);
}
else for(int j=;j<G[u.p[]].size();j++){
if(n==){
update(q, u, i,j);
}
else for(int k=;k<G[u.p[]].size();k++){
update(q, u, i,j,k);
}
}
}
}
printf("%d\n",ans);
} int main() {
while(read()){
solve(); for(int i=;i<=maxv;i++)
G[i].clear();
} return ;
}