自动搬运

查看原文

来自洛谷，原作者为

	baiABC AFOed

搬运于2025-08-24 21:30:15，当前版本为作者最后更新于2021-05-22 08:49:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面可以看这里

思路：

• 由题意可知我们不用判断迷宫的边界，因为外围都是障碍物。

• “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。