uva 1601 The Morning after Halloween code2

题目：The Morning after Halloween

题意：有n个用小写字母表示的鬼和一张地图，每个鬼都要移动到对应的大写字母，两个鬼的位置不能在一次移动中交换，问最少步数。

思路：

双向bfs。此题还可以单向bfs，见code1。

1、先将地图用图的方法表示，即在每一个空白（包括大小写字母）和四周的空白连上一条边，用单个整数表示一个空白。

2、双向bfs。即从开始和结束都进行bfs，相遇时把两次的走过的路径长加起来就是结果。

参考：

http://blog.csdn.net/qq_29169749/article/details/51420097

http://blog.csdn.net/crazysillynerd/article/details/42681579

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<sstream>
#include<queue>
using namespace std;

#define N 20
#define Num 3
#define m_step 200

int n,m,num;
int Start[Num],End[Num];
vector<int> g[N*N];
int cnt=0;
int step[m_step][m_step][m_step];
int color[m_step][m_step][m_step];

struct Node {
	int x[Num];
	Node() {}
	Node(int xx[]) {
		for(int i=0; i<num; i++) x[i]=xx[i];
	}
	Node(int one,int two,int three) {
		x[0]=one,x[1]=two,x[2]=three;
	}
	bool operator ==(const Node& other) const {
		for(int i=0; i<num; i++) {
			if(x[i]!=other.x[i]) return false;
		}
		return true;
	}
};

void init() {
	cnt=0;
	for(int i=0; i<N*N; i++) g[i].clear(),g[i].push_back(i);
	memset(step,-1,sizeof(step));
	memset(Start,0,sizeof(Start));
	memset(End,0,sizeof(End));
	memset(color,0,sizeof(color));
}

void make_G(char a[N][N]) {
	int fill[N][N]= {0};
	memset(fill,0,sizeof(fill));
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(a[i][j]!='#') {
				fill[i][j]=++cnt;
				if(i!=0&&a[i-1][j]!='#') g[cnt].push_back(fill[i-1][j]),g[fill[i-1][j]].push_back(cnt);
				if(j!=0&&a[i][j-1]!='#') g[cnt].push_back(fill[i][j-1]),g[fill[i][j-1]].push_back(cnt);
			}
		}
	}
	int S[26]= {0},E[26]= {0};
	memset(S,0,sizeof(S));
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if('A'<=a[i][j]&&a[i][j]<='Z') {
				E[a[i][j]-'A']=fill[i][j];
			}
			if('a'<=a[i][j]&&a[i][j]<='z') {
				S[a[i][j]-'a']=fill[i][j];
			}
		}
	}
	int s=-1;
	for(int i=0; i<26; i++) {
		if(S[i]) {
			++s;
			Start[s]=S[i];
			End[s]=E[i];
		}
	}
}

void dbfs() {
	Node IN=Node(Start),OUT=Node(End);
	queue<Node> quef,queb;
	quef.push(IN),queb.push(OUT);
	step[IN.x[0]][IN.x[1]][IN.x[2]]=0;
	step[OUT.x[0]][OUT.x[1]][OUT.x[2]]=0;
	while(!quef.empty()&&!queb.empty()) {

		int T=quef.size();
		while(T--) {
			Node head=quef.front();
			quef.pop();
			int a=head.x[0],b=head.x[1],c=head.x[2];
			for(int i=0; i<g[a].size(); i++) {
				for(int j=0; j<g[b].size(); j++) {
					if(g[a][i]==g[b][j]||(a==g[b][j]&&b==g[a][i])) continue;
					for(int k=0; k<g[c].size(); k++) {
						int a2=g[a][i],b2=g[b][j],c2=g[c][k];
						if((a2==c2||c2==b2||(a==c2&&c==a2)||(b==c2&&c==b2))&&c!=0) continue;
						if(color[a2][b2][c2]==0) {
							step[a2][b2][c2]=step[a][b][c]+1;
							color[a2][b2][c2]=1;
							quef.push(Node(a2,b2,c2));
						} else if(color[a2][b2][c2]==2) {
							printf("%d\n",step[a2][b2][c2]+step[a][b][c]-1);
							return;
						}
					}
				}
			}
		}

		T=queb.size();	//注意在此处更新 
		while(T--) {
			Node head=queb.front();
			queb.pop();
			int a=head.x[0],b=head.x[1],c=head.x[2];
			for(int i=0; i<g[a].size(); i++) {
				for(int j=0; j<g[b].size(); j++) {
					if(g[a][i]==g[b][j]||(a==g[b][j]&&b==g[a][i])) continue;
					for(int k=0; k<g[c].size(); k++) {
						int a2=g[a][i],b2=g[b][j],c2=g[c][k];
						if((a2==c2||c2==b2||(a==c2&&c==a2)||(b==c2&&c==b2))&&c!=0) continue;
						if(color[a2][b2][c2]==0) {
							step[a2][b2][c2]=step[a][b][c]+1;
							color[a2][b2][c2]=2;
							queb.push(Node(a2,b2,c2));
						} else if(color[a2][b2][c2]==1) {
							printf("%d\n",step[a2][b2][c2]+step[a][b][c]-1);
							return;
						}
					}
				}
			}
		}

	}
}

int main() {
	while(scanf("%d%d%d",&m,&n,&num)==3&&n&&m&&num) {
		init();
		char a[N][N];
		for(int i=0; i<n; i++) {
			getchar();
			fgets(a[i],m+1,stdin);
		}
		make_G(a);
		dbfs();
	}
	return 0;
}