题目：
w*h（w,h≤16）网格上有n(n≤3)个小写字母（代表鬼）。要求把它们分别移动到对应的大写字母里。每步可以有多个鬼同时移动（均为往上下左右4个方向之一移动），但每步结束之后任何两个鬼不能占用同一个位置，也不能在一步之内交换位置。输入保证所有空格连通，所有障碍格也连通，且任何一个2*2子网格中至少有一个障碍格。输出最少的步数。
分析：
1.又碰到了“状态”这个很玄乎的词了。以当前三个鬼的位置为状态，那就有256^3(16*16=256)个，然后三个鬼在每一个状态中的移动有5^3个，这时间和空间肯定受不了啊。
2.紫书上说，可以将空格提取出来，然后对其BFS就可以了……读完有些懵逼提取？那还不是遍历？看完代码才明白可以对每个空格子进行编号，然后存一下每个格子可以走向的格子的编号就提取出来了！！其中还对每一个状态进行了编号，这也太妙了！！还是太菜了……之后BFS就可以了。
单向BFS代码：
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1000000009
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int maxn = ;
const int dx[] = {-,,,,};
const int dy[] = {,,-,,};
inline int ID(int a,int b,int c) {
return (a<<)|(b<<)|c;
}
int s[],t[];//保存初末状态
int deg[maxn];//某个格子有多少个与之相连的格子
int G[maxn][];//保存某个格子可以去向哪些格子
inline bool conflict(int a,int b,int a2,int b2) {
return a2==b2||(a2==b&&b2==a);//如果两个鬼移动到同一个位置或位置互换则冲突
}
int d[maxn][maxn][maxn];//走到某个状态经过的步数 int bfs(){
queue<int>q;
memset(d,-,sizeof(d));
q.push(ID(s[],s[],s[]));
d[s[]][s[]][s[]] = ;
while(!q.empty()){
int u=q.front();q.pop();
int a=(u>>)&0xff,b=(u>>)&0xff,c=u&0xff;//获取该状态下，三个鬼的位置 if(a==t[]&&b==t[]&&c==t[])//如果已经找到了，就返回结果
return d[a][b][c];
for(int i=; i<deg[a]; i++){//在一步中三个鬼到底该怎么走，那就三重循环枚举所有的可能情况就可以了
int a2=G[a][i];
for(int j=; j<deg[b]; j++){
int b2=G[b][j];
if(conflict(a,b,a2,b2))continue;
for(int k=; 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]!=-) continue;
d[a2][b2][c2] = d[a][b][c]+;//记录距离
q.push(ID(a2,b2,c2));
}
}
}
}
return -;
} int main() {
//FRE();
int w,h,n;
while(scanf("%d%d%d\n",&w,&h,&n)== && n){
char maze[][];
for(int i=; i<h; i++){
fgets(maze[i],,stdin);
}
int cnt,x[maxn],y[maxn],id[maxn][maxn];
cnt=;
for(int i=; i<h; i++){//提取图中所有可以走的格子
for(int j=; 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]))t[maze[i][j]-'A'] = cnt;//记录末位置
cnt++;
}
}
}
for(int i=; i<cnt; i++){//遍历提取的格子
deg[i] = ;
for(int dir=; dir<; dir++){//记录可以从该格子走到的格子
int nx=x[i]+dx[dir],ny=y[i]+dy[dir];
if(maze[nx][ny]!='#')
G[i][deg[i]++] = id[nx][ny];
}
}
//如果起始格子不够3个就补全，让他们的起始位置和末位置重合就可以了
if(n==){
deg[cnt] = ; G[cnt][]=cnt;s[]=t[] = cnt++;
}
if(n==){
deg[cnt] = ; G[cnt][]=cnt;s[]=t[] = cnt++;
}
printf("%d\n",bfs());
}
return ;
}
这个题目也可以用双向BFS来做，做完这个题，对双向BFS有了进一步的理解。那这里的正向就是遍历小写字母，反向就是遍历大写字母。当小写字母和大写字母的位置重合之后，就是得到的答案。
双向BFS代码：
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1000000009
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int maxn = ;
const int dx[] = {-, , , , };
const int dy[] = {, , -, , };
inline int ID(int a, int b, int c) {
return (a << ) | (b << ) | c;
}
int s[], t[]; //保存初末状态
int deg[maxn];//某个格子有多少个与之相连的格子
int G[maxn][];//保存某个格子可以去向哪些格子
inline bool conflict(int a, int b, int a2, int b2) {
return a2 == b2 || (a2 == b && b2 == a); //如果两个鬼移动到同一个位置或位置互换则冲突
}
int d[maxn][maxn][maxn], vis[maxn][maxn][maxn]; //走到某个状态经过的步数 int bfs() {
queue<int> que,que_rev;
d[s[]][s[]][s[]] = ;
d[t[]][t[]][t[]] = ; que.push(ID(s[],s[],s[]));
que_rev.push(ID(t[],t[],t[])); vis[s[]][s[]][s[]] = ;
vis[t[]][t[]][t[]] = ; while(!que.empty() && !que_rev.empty()){
int sza = que.size(),szb=que_rev.size();
while(sza--){
int u=que.front(); que.pop();
int a=(u>>)&0xff,b=(u>>)&0xff,c=(u&0xff);
for(int i=; i<deg[a]; i++){
int a2 = G[a][i];
for(int j=; j<deg[b]; j++){
int b2 = G[b][j];
if(conflict(a,b,a2,b2)) continue;
for(int k=; k<deg[c]; k++){
int c2 = G[c][k];
if(conflict(a,c,a2,c2)) continue;
if(conflict(b,c,b2,c2)) continue; if(vis[a2][b2][c2]==){
vis[a2][b2][c2] = ;
d[a2][b2][c2] = d[a][b][c]+;
que.push(ID(a2,b2,c2));
}else if(vis[a2][b2][c2]==){
return d[a2][b2][c2]+d[a][b][c]+;
}
}
}
}
}
while(szb--){
int u=que_rev.front(); que_rev.pop();
int a=(u>>)&0xff, b=(u>>)&0xff,c=(u&0xff);
for(int i=; i<deg[a]; i++){
int a2 = G[a][i];
for(int j=; j<deg[b]; j++){
int b2=G[b][j];
if(conflict(a,b,a2,b2))continue;
for(int k=; k<deg[c]; k++){
int c2=G[c][k];
if(conflict(a,c,a2,c2))continue;
if(conflict(b,c,b2,c2))continue; if(vis[a2][b2][c2]==){
vis[a2][b2][c2]=;
d[a2][b2][c2] = d[a][b][c]+;
que_rev.push(ID(a2,b2,c2));
}else if(vis[a2][b2][c2]==){
return d[a2][b2][c2]+d[a][b][c]+;
}
}
}
}
}
}
return -;
} int main() {
//FRE();
int w, h, n;
while(scanf("%d%d%d\n", &w, &h, &n) == && n) {
char maze[][];
memset(d, -, sizeof(d));
memset(vis, , sizeof(vis));
int cnt, x[maxn], y[maxn], id[maxn][maxn];
cnt = ; for(int i = ; i < h; i++) {
fgets(maze[i], , stdin);
} for(int i = ; i < h; i++) { //提取图中所有可以走的格子
for(int j = ; 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])) {
t[maze[i][j] - 'A'] = cnt; //记录末位置
}
cnt++;
}
}
}
for(int i = ; i < cnt; i++) { //遍历提取的格子
deg[i] = ;
for(int dir = ; dir < ; dir++) { //记录可以从该格子走到的格子
int nx = x[i] + dx[dir], ny = y[i] + dy[dir];
if(maze[nx][ny] != '#')
{ G[i][deg[i]++] = id[nx][ny]; }
}
}
//如果起始格子不够3个就补全，让他们的起始位置和末位置重合就可以了
if(n == ) {
deg[cnt] = ;
G[cnt][] = cnt;
s[] = t[] = cnt++;
}
if(n == ) {
deg[cnt] = ;
G[cnt][] = cnt;
s[] = t[] = cnt++;
}
printf("%d\n", bfs());
}
return ;
}