The Morning after Halloween UVA - 1601(bfs)

题目大意：小写字母到对应的大写字母是最短路径是多少？其中小写字母有多个，最多三个，然后每个字母有五种方向，上下左右不动，#称为墙不可走，其他是可走，称为走廊。
思路：
1：给可以走的走廊编号，对每条走廊建邻接表，然后bfs遍历这张表找最短路（遍历有点技巧，O(N^3)的邻接表遍历）。
2：学到的新技巧，对于三个数给他编码成一个数存到queue，然后解码取出三个数，编码：((a<<16)|(b<<8)|c); 解码：int a=((tem>>16)&0xff);
int b=((tem>>8)&0xff);
int c=((tem)&0xff);
原理很简单，就是给int划区域，编码的最大值255，很容易证明
3：因为输入的个数是变化的，所以在n<=2的时候终点与起点无法判断，这个时候创建虚拟节点，把没有输入的字母指向同一地区，并且设置永远不可动。
4：不可交换走，不能一个格子两个字母，把这种情况pass掉。
总结：这是我写过最难的bfs，关键是建立邻接表O（n^3）遍历这个比较难想到。
代码：

#include<queue>
#include<iostream>
#include<cstring>
#include<string.h>
using namespace std;

/* 5 5 2 ##### #A#B# # # #b#a# ##### */

const int maxn=300+10;
char maze[20][20];
int G[maxn][maxn];
int dis[maxn][maxn][maxn];
int dir[5][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}};
int s[3],e[3];
int dge[maxn];

int Code(int a,int b,int c){
	return ((a<<16)|(b<<8)|c);
}

bool canwlak(int a,int b,int a1,int b1){
	return (a1==b1||(a1==b&&b1==a));
}

int bfs(){
	memset(dis,-1,sizeof(dis)); 
	queue<int>st;
	st.push(Code(s[0],s[1],s[2]));
	dis[s[0]][s[1]][s[2]]=0;
	while(!st.empty()){
		int tem=st.front();st.pop();
		int a=((tem>>16)&0xff);
		int b=((tem>>8)&0xff);
		int c=((tem)&0xff);
		if(a==e[0]&&b==e[1]&&c==e[2]){
			return dis[a][b][c];
		}
		for(int i=0;i<dge[a];i++){
			int x=G[a][i];
			for(int j=0;j<dge[b];j++){
				int y=G[b][j];
				if(canwlak(a,b,x,y))continue;
				for(int k=0;k<dge[c];k++){
					int z=G[c][k];
					if(canwlak(a,c,x,z))continue;
					if(canwlak(b,c,y,z))continue;
					if(dis[x][y][z]!=-1)continue;
					dis[x][y][z]=dis[a][b][c]+1;
					st.push(Code(x,y,z));
				}
			}
		}
	}
}
int main(){
	int w,h,n;
	while(scanf("%d%d%d\n",&w,&h,&n)&&(w||h||n)){
		memset(G,0,sizeof(G));
		for(int i=0;i<h;i++)
		fgets(maze[i],20,stdin);
		
		
		int x[200],y[200],id[200][200];
		int cnt=0;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(maze[i][j]!='#'){
					x[cnt]=i;y[cnt]=j;id[i][j]=cnt;
					if(islower(maze[i][j])){
						s[maze[i][j]-'a']=cnt;

					}else if(isupper(maze[i][j])){
						e[maze[i][j]-'A']=cnt;
					}
					cnt++;
				}
			}
		}
		
		
		for(int i=0;i<cnt;i++){//给每条边建立邻接表 
			dge[i]=0;
			for(int j=0;j<5;j++){
				int fx=x[i]+dir[j][0];
				int fy=y[i]+dir[j][1];
				if(maze[fx][fy]!='#'){
					G[i][dge[i]++]=id[fx][fy];
				}
			}
		}
		// add fakes nodes so that in each case we have 3 ghosts. this makes the code shorter
		if(n <= 2) { dge[cnt] = 1; G[cnt][0] = cnt; s[2] = e[2] = cnt++; }
        if(n <= 1) { dge[cnt] = 1; G[cnt][0] = cnt; s[1] = e[1] = cnt++; }

		printf("%d\n",bfs());
	}
}