题解【P1778 万圣节后的早晨】
题面可以看这里
思路：
-
由题意可知我们不用判断迷宫的边界，因为外围都是障碍物。
-
“Any 2 × 2 area on any map has at least one sharp.”就是说有许多格子都是障碍物，所以我们可以把所有的空格提出来建一张图，能大大节约时间。
-
建图时可以让额外的结点形成自环，让我们每次都有三个鬼，方便处理。
-
现在普通 BFS 已可以通过本题，但还可以继续优化，如用双向 BFS、A* 等算法。
代码：
普通 BFS:
#include <bits/stdc++.h>
using namespace std;
int G[150][5], deg[150], st[3], ed[3], d[150][150][150];
//deg: 每个结点的出度（最大为 5，四个方向和原地不动）
//d: 每个状态到起点状态的距离
int mm(int a, int b, int c) {return (a<<16) | (b<<8) | c;}// 二进制状态压缩
bool ct(int a, int b, int x, int y){return b == y || (a == y && b == x);}
// 返回 a -> b 的鬼和 x -> y 的鬼路线是否冲突
int bfs()
{
memset(&d[0][0][0], -1, sizeof d);
queue <int> q;
q.push(mm(st[0], st[1], st[2]));
d[st[0]][st[1]][st[2]] = 0;
while(!q.empty())
{
int x = q.front(), a = x >> 16, b = (x >> 8) & 0xff, c = x & 0xff;
q.pop();
if(a == ed[0] && b == ed[1] && c == ed[2]) return d[a][b][c];
for(int i = 0; i < deg[a]; ++i)
for(int j = 0; j < deg[b]; ++j)
{
if(ct(a, G[a][i], b, G[b][j])) continue;
for(int k = 0; k < deg[c]; ++k)
{
if(ct(a, G[a][i], c, G[c][k]) || ct(b, G[b][j], c, G[c][k]) || d[G[a][i]][G[b][j]][G[c][k]] != -1) continue;
d[G[a][i]][G[b][j]][G[c][k]] = d[a][b][c]+1;
q.push(mm(G[a][i], G[b][j], G[c][k]));
}
}
}
return -1;
}
int main()
{
int w, h, n;
char s[20][20];
while(scanf("%d%d%d", &w, &h, &n), w || h || n)
{
int cnt = 0, id[20][20]; // id: 空格在图中结点编号
memset(deg, 0, sizeof deg);
for(int i = 0; i < h; ++i)
{ // 处理好输入，顺便建图
scanf(" ");
for(int j = 0; j < w; ++j)
{
s[i][j] = getchar();
if(s[i][j] != '#')
{
id[i][j] = ++cnt;
G[cnt][deg[cnt]++] = cnt;
if(s[i-1][j] != '#'){G[cnt][deg[cnt]++] = id[i-1][j]; G[id[i-1][j]][deg[id[i-1][j]]++] = cnt;}
if(s[i][j-1] != '#'){G[cnt][deg[cnt]++] = id[i][j-1]; G[id[i][j-1]][deg[id[i][j-1]]++] = cnt;}
if(islower(s[i][j])) st[s[i][j]-'a'] = cnt;
else if(isupper(s[i][j])) ed[s[i][j]-'A'] = cnt;
}
}
}
/* 虚拟结点 */
if(n <= 2) {deg[++cnt] = 1; G[cnt][0] = cnt; st[2] = ed[2] = cnt;}
if(n == 1) {deg[++cnt] = 1; G[cnt][0] = cnt; st[1] = ed[1] = cnt;}
printf("%d\n", bfs());
}
return 0;
}双向 BFS:
#include <bits/stdc++.h>
using namespace std;
int G[150][5], deg[150], st[3], ed[3], d1[150][150][150], d2[150][150][150];
int mm(int a, int b, int c) {return (a<<16) | (b<<8) | c;}
bool ct(int a, int b, int x, int y){return b == y || (a == y && b == x);}
int bfs()
{
memset(&d1[0][0][0], -1, sizeof d1);
memset(&d2[0][0][0], -1, sizeof d2);
queue <int> q1, q2;
q1.push(mm(st[0], st[1], st[2]));
d1[st[0]][st[1]][st[2]] = 0;
q2.push(mm(ed[0], ed[1], ed[2]));
int n1, n2, x1, x2;
n2 = n1 = 1;
x1 = x2 = 0;
do {
if(!n2 || x1 < x2)
{
int x = q1.front(), a = x >> 16, b = (x >> 8) & 0xff, c = x & 0xff;
q1.pop(); --n1;
if(d2[a][b][c] != -1) return d1[a][b][c] + d2[a][b][c];
if(d1[a][b][c] > x1){++x1; q1.push(x); ++n1; continue;}
for(int i = 0; i < deg[a]; ++i)
for(int j = 0; j < deg[b]; ++j)
{
if(ct(a, G[a][i], b, G[b][j])) continue;
for(int k = 0; k < deg[c]; ++k)
{
if(ct(a, G[a][i], c, G[c][k]) || ct(b, G[b][j], c, G[c][k]) || d1[G[a][i]][G[b][j]][G[c][k]] != -1) continue;
d1[G[a][i]][G[b][j]][G[c][k]] = d1[a][b][c]+1;
q1.push(mm(G[a][i], G[b][j], G[c][k]));
++n1;
}
}
}
else
{
int x = q2.front(), a = x >> 16, b = (x >> 8) & 0xff, c = x & 0xff;
q2.pop(); --n2;
if(d1[a][b][c] != -1) return d1[a][b][c] + d2[a][b][c];
if(d2[a][b][c] > x2){++x2; q2.push(x); ++n2; continue;}
for(int i = 0; i < deg[a]; ++i)
for(int j = 0; j < deg[b]; ++j)
{
if(ct(a, G[a][i], b, G[b][j])) continue;
for(int k = 0; k < deg[c]; ++k)
{
if(ct(a, G[a][i], c, G[c][k]) || ct(b, G[b][j], c, G[c][k]) || d2[G[a][i]][G[b][j]][G[c][k]] != -1) continue;
d2[G[a][i]][G[b][j]][G[c][k]] = d2[a][b][c]+1;
q2.push(mm(G[a][i], G[b][j], G[c][k]));
++n2;
}
}
}
} while(n1 || n2);
return -1;
}
int main()
{
int w, h, n;
char s[20][20];
while(scanf("%d%d%d", &w, &h, &n), w || h || n)
{
int cnt = 0, id[20][20];
memset(deg, 0, sizeof deg);
for(int i = 0; i < h; ++i)
{
scanf(" ");
for(int j = 0; j < w; ++j)
{
s[i][j] = getchar();
if(s[i][j] != '#')
{
id[i][j] = ++cnt;
G[cnt][deg[cnt]++] = cnt;
if(s[i-1][j] != '#'){G[cnt][deg[cnt]++] = id[i-1][j]; G[id[i-1][j]][deg[id[i-1][j]]++] = cnt;}
if(s[i][j-1] != '#'){G[cnt][deg[cnt]++] = id[i][j-1]; G[id[i][j-1]][deg[id[i][j-1]]++] = cnt;}
if(islower(s[i][j])) st[s[i][j]-'a'] = cnt;
else if(isupper(s[i][j])) ed[s[i][j]-'A'] = cnt;
}
}
}
if(n <= 2) {deg[++cnt] = 1; G[cnt][0] = cnt; st[2] = ed[2] = cnt;}
if(n == 1) {deg[++cnt] = 1; G[cnt][0] = cnt; st[1] = ed[1] = cnt;}
printf("%d\n", bfs());
}
return 0;
}双倍经验：UVA1601。