The Morning after Halloween
这道题可以用bfs做，但是前期处理比较复杂，主要分为以下几步：
1.建图；
题目给的‘#’太多，一个状态有三个字符，相当于我们每次一个状态到下一个状态都要判断三次，每次呢又有5种不同的走法，相当于每次转状态都要枚举5^3个；
我们可以单独把空格进行编号，根据空格的连接关系，连成一张图，然后遍历这张图就可以了；我用的是链式前向星进行连接；
2.当n<=2时的处理；
我们可以先根据n=3，把起点和终点全部找出来。当n<=2时，我们赋值给没有的那几个点一个起点和终点，然后连接这一个点成一条边，相当于自环；
3.细节的处理；
这题细节特别多，题目没有说鬼魂要用a，b，c来表示，只是说小写字母；每个鬼魂可以同时移动，但是不可以互换位置，不可以同时在一个点；鬼魂可以不走，所以要自身连成环，相当于没走；
代码：
#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
#define lson k<<1
#define rson k<<1|1
#define inf 0x3f3f3f3f
//ios::sync_with_stdio(false);
using namespace std;
const int N=200100;
const int M=1000100;
const LL mod=998244353;
string s[20];
int a[20][20];
bool vis[200][200][200];
int sa,sb,sc,ea,eb,ec;
struct Nod{int to,nex;
}edge[N];
int cnt;
int head[N];
void add(int p,int q){edge[cnt].to=q;edge[cnt].nex=head[p];head[p]=cnt++;
}
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int f[200];
struct Node{int ta,tb,tc,step;
};
void bfs(){queue<Node>qu;Node n1;n1.ta=sa,n1.tb=sb,n1.tc=sc,n1.step=0;vis[sa][sb][sc]=true;qu.push(n1);while(!qu.empty()){Node n2=qu.front();qu.pop();if(n2.ta==ea&&n2.tb==eb&&n2.tc==ec){cout<<n2.step<<endl;return;}for(int i=head[n2.ta];~i;i=edge[i].nex){int va=edge[i].to;for(int j=head[n2.tb];~j;j=edge[j].nex){int vb=edge[j].to;for(int k=head[n2.tc];~k;k=edge[k].nex){int vc=edge[k].to;if(va==vb||va==vc||vb==vc||vis[va][vb][vc]) continue;if(va==n2.ta&&vb==n2.tb&&vc==n2.tc) continue;if(va==n2.tb&&vb==n2.ta) continue;if(va==n2.tc&&vc==n2.ta) continue;if(vb==n2.tc&&vc==n2.tb) continue;vis[va][vb][vc]=true;Node n3;n3.ta=va,n3.tb=vb,n3.tc=vc,n3.step=n2.step+1;qu.push(n3);}}}}
}
void init(){memset(head,-1,sizeof(head));cnt=0;sa=sb=sc=ea=eb=ec=0;memset(vis,false,sizeof(vis));memset(f,0,sizeof(f));
}
int main(){ios::sync_with_stdio(false);int w,h,n;while(cin>>w>>h>>n){if(w==0&&h==0&&n==0) break;init(); getline(cin,s[0]);//吃回车for(int i=1;i<=h;i++) getline(cin,s[i]);int ans=0;for(int i=1;i<=h;i++){for(int j=0;j<w;j++){if(s[i][j]!='#') a[i][j]=++ans;if((s[i][j]>='A'&&s[i][j]<='Z')||(s[i][j]>='a'&&s[i][j]<='z')){f[s[i][j]-'A']=ans;}}}int ok=0;for(int i=0;i<=26;i++){if(f[i]) ok++;if(ok==1&&f[i]) ea=f[i],sa=f[i+32];else if(f[i]&&ok==2) eb=f[i],sb=f[i+32];else if(ok==3&&f[i]) ec=f[i],sc=f[i+32];}for(int i=1;i<=h;i++){for(int j=0;j<w;j++){if(s[i][j]!='#'){add(a[i][j],a[i][j]);//自身成环，相当于不走for(int k=0;k<4;k++){int u=i+dx[k];int v=j+dy[k];if(u<0||u>=h||v<0||v>=w||s[u][v]=='#') continue;add(a[i][j],a[u][v]);}}}}if(n==2){sc=++ans;ec=ans;add(ans,ans);}if(n==1){sb=++ans;eb=ans;add(ans,ans);sc=++ans;ec=ans;add(ans,ans);}bfs();}return 0;
}