//测试数据
/*
5 5 2
#####
#A#B#
# #
#b#a#
#####
16 4 3
################
## ########## ##
# ABCcba #
################
16 16 3
################
### ## # ##
## # ## # c#
# ## ########b#
# ## # # # #
# # ## # # ##
## a# # # # #
### ## #### ## #
## # # # #
# ##### # ## ##
#### #B# # #
## C# # ###
# # # ####### #
# ###### A## #
# # ##
################
0 0 0
*/#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
using namespace std;
const int maxs=20;
const int maxn=200;int s[3],t[3];
int deg[maxn],G[maxn][5]; //G[][]是邻接表保存，deg[i]保存第i个点有几个相连点
int dis[maxn][maxn][maxn]; //判重同时也记录距离 int ID(int a,int b,int c) //三位数变为一位数记录
{return (a<<16)|(b<<8)|c; //0|1=1;
}
bool conflict(int a,int b,int a2,int b2)
{return b2==a2||(a==b2&&b==a2); //不能穿过和重合
}
int bfs()
{queue<int> q;q.push(ID(s[0],s[1],s[2]));memset(dis,-1,sizeof(dis)); //-1表示未走过 dis[s[0]][s[1]][s[2]]=0;while(!q.empty()){int u=q.front();q.pop();int a=(u>>16)&0xff,b=(u>>8)&0xff,c=u&0xff; //1&0=0; (A|0)&1=A; if(a==t[0]&&b==t[1]&&c==t[2]) return dis[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(a,c,a2,c2)) continue;if(conflict(b,c,b2,c2)) continue;if(dis[a2][b2][c2]!=-1) continue;dis[a2][b2][c2]=dis[a][b][c]+1;q.push(ID(a2,b2,c2));}}}}return -1;
}
int main()
{int w,h,n;while(scanf("%d%d%d",&w,&h,&n)==3&&n){getchar(); //读取一个回车 char maze[20][20];for(int i=0;i<h;i++) fgets(maze[i],20,stdin); //比scanf("%c",&maze[i][j])方便或者用cin>>maze[i]但比较慢; int cnt=0,x[maxn],y[maxn],id[maxs][maxs];for(int i=0;i<h;i++)for(int j=0;j<w;j++){char ch=maze[i][j];if(ch!='#'){x[cnt]=i;y[cnt]=j; //记录每个编号的横纵坐标，方便等下记录与其连接的节点 id[i][j]=cnt; //对每个非'#'节点编号，cnt表示编号 if(islower(ch)) s[ch-'a']=cnt;else if(isupper(ch)) t[ch-'A']=cnt;cnt++;}}const int dx[]={1,-1,0, 0,0}; //可以走五步 const int dy[]={0, 0,1,-1,0};for(int i=0;i<cnt;i++){deg[i]=0;for(int dir=0;dir<5;dir++) {int nx=x[i]+dx[dir];int ny=y[i]+dy[dir];if(maze[nx][ny]!='#') G[i][deg[i]++]=id[nx][ny]; //G[i][0~deg[i]-1]是保存从i点出发可到的点; }}if(n<=2) deg[cnt]=1,G[cnt][0]=cnt,s[2]=t[2]=cnt++; //对于不到3个的，新建一个点，起点终点在同一位置且该点只能到该点，即自环 if(n<=1) deg[cnt]=1,G[cnt][0]=cnt,s[1]=t[1]=cnt++;printf("%d\n",bfs());}return 0;
}
单向稍微改编就能得到双向BFS
正着搜一个节点，反着搜一个节点 ，当遇到正反搜索都搜过的节点就表明已经找到解了。
接下来是双向BFS代码
用时从940ms变为550ms
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
using namespace std;
const int maxs=20;
const int maxn=200;int s[3],t[3];
int deg[maxn],G[maxn][5]; //G[][]是邻接表保存，deg[i]保存第i个点有几个相连点
int dis[maxn][maxn][maxn],dis_pback[maxn][maxn][maxn]; //判重同时也记录距离 int ID(int a,int b,int c) //三位数变为一位数记录
{return (a<<16)|(b<<8)|c; //0|1=1;
}
bool conflict(int a,int b,int a2,int b2)
{return b2==a2||(a==b2&&b==a2); //不能穿过和重合
}
int bfs(queue<int>& q,int d[maxn][maxn][maxn]) {int u = q.front(); q.pop();int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff;if(dis[a][b][c]!=-1&&dis_back[a][b][c]!=-1) return dis[a][b][c]+dis_back[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(a, c, a2, c2)) continue;if(conflict(b, c, b2, c2)) continue;if(d[a2][b2][c2] != -1) continue;d[a2][b2][c2] = d[a][b][c]+1;q.push(ID(a2, b2, c2));}}}return -1;
}
int solve()
{queue<int> q;q.push(ID(s[0],s[1],s[2]));memset(dis,-1,sizeof(dis)); dis[s[0]][s[1]][s[2]]=0; queue<int> q_back;q_back.push(ID(t[0],t[1],t[2])); //终点出发memset(dis_back,-1,sizeof(dis_back)); dis_back[t[0]][t[1]][t[2]]=0;int ans;while(1) //正着搜一个节点，反着搜一个节点 {ans=bfs(q,dis);if(ans!=-1) return ans;ans=bfs(q_back,dis_back);if(ans!=-1) return ans;}return -1;
}
int main()
{int w,h,n;while(scanf("%d%d%d",&w,&h,&n)==3&&n){getchar(); //读取一个回车 char maze[20][20];for(int i=0;i<h;i++) fgets(maze[i],20,stdin); //比scanf("%c",&maze[i][j])方便或者用cin>>maze[i]但比较慢; int cnt=0,x[maxn],y[maxn],id[maxs][maxs];for(int i=0;i<h;i++)for(int j=0;j<w;j++){char ch=maze[i][j];if(ch!='#'){x[cnt]=i;y[cnt]=j; //记录每个编号的横纵坐标，方便等下记录与其连接的节点 id[i][j]=cnt; //对每个非'#'节点编号，cnt表示编号 if(islower(ch)) s[ch-'a']=cnt;else if(isupper(ch)) t[ch-'A']=cnt;cnt++;}}const int dx[]={1,-1,0, 0,0}; //可以走五步 const int dy[]={0, 0,1,-1,0};for(int i=0;i<cnt;i++){deg[i]=0;for(int dir=0;dir<5;dir++) {int nx=x[i]+dx[dir];int ny=y[i]+dy[dir];if(maze[nx][ny]!='#') G[i][deg[i]++]=id[nx][ny]; //G[i][0~deg[i]-1]是保存从i点出发可到的点; }}if(n<=2) deg[cnt]=1,G[cnt][0]=cnt,s[2]=t[2]=cnt++; //对于不到3个的，新建一个点，起点终点在同一位置且该点只能到该点，即自环 if(n<=1) deg[cnt]=1,G[cnt][0]=cnt,s[1]=t[1]=cnt++;printf("%d\n",solve());}return 0;
}