分析:如果以当前3个小写字母的位置为状态，则问题转化为图上的最短路问题。但是如果每次都判断小写字母的下一步是否合法，那就是说每次移动都需要判断5^3,肯定会超时。可以把所有可以移动的格子找出来建立一张图，就是把障碍物给删除，统计每个可以空格或者有鬼的格子可以移动到哪些格子，这样在判断的时候就节省了许多时间。然后bfs找最短路。注意读入的时候要多读入一个换行符，因为scanf的缓冲区用完以后，必须要读入一个字符才能才能结束读入，另外就是建图，过程，这个题的建图我给满分。
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "string" 5 #include "queue" 6 using namespace std; 7 const int maxn=200; 8 int s[3],t[3]; 9 int dx[]={-1,1,0,0,0}; 10 int dy[]={0,0,-1,1,0}; 11 int ind[maxn]; 12 int g[maxn][5]; 13 int d[maxn][maxn][maxn]; 14 bool conflict(int a,int b,int a2,int b2){ 15 return a2==b2||(a2==b&&b2==a); 16 } 17 typedef struct 18 { 19 int a,b,c; 20 }Node; 21 int bfs() 22 { 23 queue<Node> que; 24 memset(d,-1,sizeof(d)); 25 Node f; 26 f.a=s[0],f.b=s[1],f.c=s[2]; 27 d[s[0]][s[1]][s[2]]=0; 28 que.push(f); 29 while(!que.empty()){ 30 Node u=que.front(); que.pop(); 31 int a=u.a,b=u.b,c=u.c; 32 if(a==t[0]&&b==t[1]&&c==t[2]) return d[a][b][c]; 33 for(int i=0;i<ind[a];i++){ 34 int a2=g[a][i]; 35 for(int j=0;j<ind[b];j++){ 36 int b2=g[b][j]; 37 if(conflict(a,b,a2,b2)) continue; 38 for(int k=0;k<ind[c];k++){ 39 int c2=g[c][k]; 40 if(conflict(a,c,a2,c2)) continue; 41 if(conflict(b,c,b2,c2)) continue; 42 if(d[a2][b2][c2]!=-1) continue; 43 Node zz; 44 zz.a=a2,zz.b=b2,zz.c=c2; 45 d[a2][b2][c2]=d[a][b][c]+1; 46 que.push(zz); 47 } 48 } 49 } 50 } 51 return -1; 52 } 53 int main() 54 { 55 int w,h,n; 56 while(scanf("%d%d%d ",&w,&h,&n)==3&&n) 57 { 58 string str[maxn]; 59 for(int i=0;i<h;i++) 60 getline(cin,str[i]); 61 int cnt=0; 62 int x[maxn],y[maxn],id[maxn][maxn]; 63 for(int i=0;i<h;i++){ //建图 64 for(int j=0;j<w;j++){ 65 if(str[i][j]!='#'){ 66 x[cnt]=i,y[cnt]=j,id[i][j]=cnt; 67 if(islower(str[i][j])) s[str[i][j]-'a']=cnt; 68 else if(isupper(str[i][j])) t[str[i][j]-'A']=cnt; 69 ++cnt; 70 } 71 } 72 } 73 for(int i=0;i<cnt;i++){ 74 ind[i]=0; 75 for(int dir=0;dir<5;dir++){ 76 int nx=x[i]+dx[dir],ny=y[i]+dy[dir]; 77 if(str[nx][ny]!='#') 78 g[i][ind[i]++]=id[nx][ny]; 79 } 80 } 81 if(n<=2){ 82 ind[cnt]=1;g[cnt][0]=cnt; s[2]=t[2]=cnt++; 83 } 84 if(n<=1){ 85 ind[cnt]=1;g[cnt][0]=cnt; s[1]=t[1]=cnt++; 86 } 87 printf("%d ",bfs()); 88 89 } 90 }