但是我们还不是很清楚每一次的状态怎么储存？我们可以用一个结构体，将每次的位置存起来，但是这个程序中用了一个更好的储存方法：我们知道最大的格数是16*16个，也就是256个，那么我们转换为二进制表示就是8位数，那么我们可以使用24位的二进制表示啊！然后我们再进行解压缩，所以这就是很神奇的地方！
普通BFS
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
//const int maxn = 1e6 + 5;
const double PI = acos(-1.0);
typedef long long ll;
using namespace std; const int maxn = ;
const int maxs = ;
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]; //记录每个编号为i的空格周围可以走的步数
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() {
int w, h, n; while (scanf("%d%d%d", &w, &h, &n) == && n) {
char maze[][];
for (int i = ; i < h; i++) fgets(maze[i], , stdin); int cnt, x[maxn], y[maxn], id[maxs][maxs];
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 xx = x[i] + dx[dir], yy = y[i] + dy[dir];
if (maze[xx][yy] != '#') G[i][deg[i]++] = id[xx][yy];
}
} 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
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
//const int maxn = 1e6 + 5;
const double PI = acos(-1.0);
typedef long long ll;
using namespace std; const int maxn = ;
const int maxs = ;
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]; //记录每个编号为i的空格周围可以走的步数
int G[maxn][];
char maze[maxn][maxn];
int color[maxn][maxn][maxn]; inline bool conflict(int a, int b, int a2, int b2) {
//两个鬼是exchange位置（违反第2条）
//两个鬼移动到同一个格子（违反第1条）
return a2 == b2 || (a2 == b && b2 == a);
} int d1[maxn][maxn][maxn]; int bfs() {
queue<int> qf;
queue<int> qb; d1[s[]][s[]][s[]] = ;
d1[t[]][t[]][t[]] = ; qf.push(ID(s[], s[], s[]));
qb.push(ID(t[], t[], t[])); while (!qf.empty() || !qb.empty()) {
int fnum = qf.size(), bnum = qb.size();
while (fnum--) {
int u = qf.front(); qf.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) || conflict(b, c, b2, c2)) continue;
if (color[a2][b2][c2] == ) {
d1[a2][b2][c2] = d1[a][b][c] + ;
color[a2][b2][c2] = ;
qf.push(ID(a2, b2, c2));
}
else if (color[a2][b2][c2] == ) {
return d1[a][b][c] + d1[a2][b2][c2];
}
}
}
}
}
while (bnum--) {
int u = qb.front(); qb.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) || conflict(b, c, b2, c2)) continue;
if (color[a2][b2][c2] == ) {
d1[a2][b2][c2] = d1[a][b][c] + ;
color[a2][b2][c2] = ;
qb.push(ID(a2, b2, c2));
}
else if (color[a2][b2][c2] == ) {
return d1[a][b][c] + d1[a2][b2][c2];
}
}
}
}
}
}
return -;
} int main() {
int w, h, n;
while (scanf("%d%d%d", &w, &h, &n) == , n) {
for (int i = ; i < h; i++) fgets(maze[i], , stdin);
int cnt = ;
int x[maxn], y[maxn];
int id[maxs][maxs];
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++) {
for (int j = ; j < ; j++) {
int xx = x[i] + dx[j], yy = y[i] + dy[j];
if (maze[xx][yy] != '#') G[i][deg[i]++] = id[xx][yy];
}
} if (n <= ) {
deg[cnt] = ;
G[cnt][] = cnt;
s[] = t[] = cnt++;
}
if (n <= ) {
deg[cnt] = ;
G[cnt][] = cnt;
s[] = t[] = cnt++;
} memset(d1, , sizeof d1);
memset(color, , sizeof color); if (s[] == t[] && s[] == t[] && s[] == t[]) printf("0\n");
else printf("%d\n", bfs());
}
return ;
}