🧩 题目名称：Ghosts in the Haunted House（幽灵移动）

📌 题目大意

在一个迷宫状的房子里，有最多三个幽灵，它们起始时被“灵异事件”移动到了错误位置。现在你要控制它们回到各自的目标位置。每一步中，你可以同时移动所有幽灵，规则如下：

• 每个幽灵每步可以原地不动或向上下左右移动一格；
• 幽灵不能穿墙；
• 幽灵不能在同一个格子重叠；
• 幽灵不能在同一步交换位置；
• 你需要计算最少的步数使所有幽灵都回到目标点。

✅ 解题思路

本题为典型多点状态搜索 + 双向 BFS问题。

核心思路：

1. 地图预处理：将地图中的每个非墙格子编号，记录幽灵的起点和终点编号。

2. 合法移动建图：对于每个非墙格子，将其可以到达的相邻非墙格子加入邻接表。

3. 双向 BFS（双向广搜）：

   • 从起点状态开始正向 BFS；
   • 从终点状态开始反向 BFS；
   • 当两边在中间某个状态相遇时，即为最短路径。

状态表示：

使用三元组 (a, b, c) 表示三个幽灵当前所在的位置编号，配合一个 step 表示当前步数。

🧠 难点处理

• 状态多（最多 $180^3$ 种组合），必须剪枝；
• 状态冲突判断（如交换位置）；
• 幽灵个数不足 3 个时，需要使用哑结点补齐。

🧾 完整代码 + 中文注释

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cstdlib>
#include <string>
using namespace std;
#define reg register
const int dx[] = {0, 1, -1, 0, 0}, dy[] = {0, 0, 0, 1, -1};
int n, m, Gh;
string mp[17];
int S[4], T[4];
int id[180][180], cnt, X[180], Y[180];
int vis1[180][180][180], vis2[180][180][180];
vector <int> ve[180];

struct date {
    int a, b, c;
    int stp;
};

bool ok(int x1, int y1, int x2, int y2) {
    if (x2 == y2) return 0;
    if (x1 == y2 and y1 == x2) return 0;
    return 1;
}

int main()
{
    while(1) 
    {
        for (reg int i = 1 ; i <= cnt ; i ++) ve[i].clear();
        cnt = 0;
        scanf("%d%d%d", &m, &n, &Gh);
        if (!n and !m and !Gh) break;
        char c;
        while((c = getchar()) || 23333) if(c == '\n') break;
        for (reg int i = 1 ; i <= n ; i ++)
        {
            getline(cin, mp[i]);
            for (reg int j = 0 ; j < m ; j ++)
            {
                if (mp[i][j] != '#') 
                    id[i][j + 1] = ++cnt, X[cnt] = i, Y[cnt] = j + 1;
                if (mp[i][j] >= 'a' and mp[i][j] <= 'c') S[mp[i][j] - 'a' + 1] = id[i][j + 1];
                if (mp[i][j] >= 'A' and mp[i][j] <= 'C') T[mp[i][j] - 'A' + 1] = id[i][j + 1];
            }
        }
        for (reg int i = 1 ; i <= n ; i ++)
        {
            for (reg int j = 1 ; j <= m ; j ++)
            {
                if (mp[i][j - 1] == '#') continue;
                for (reg int k = 0 ; k <= 4 ; k ++)
                {
                    int ti = i + dx[k], tj = j + dy[k];
                    if (ti <= 0 or ti > n or tj <= 0 or tj > m or mp[ti][tj - 1] == '#') continue;
                    ve[id[i][j]].push_back(id[ti][tj]);
                }
            }
        }
        if (Gh == 1) {
            S[2] = cnt + 1, T[2] = cnt + 1;
            S[3] = cnt + 2, T[3] = cnt + 2;
        }
        if (Gh == 2) {
            S[3] = cnt + 1, T[3] = cnt + 1;
        }
        ve[cnt + 1].push_back(cnt + 1);
        ve[cnt + 2].push_back(cnt + 2);
        
        queue <date> q1, q2;
        q1.push((date){S[1], S[2], S[3], 0});
        q2.push((date){T[1], T[2], T[3], 0});
        memset(vis1, 0, sizeof vis1);
        memset(vis2, 0, sizeof vis2);
        vis1[S[1]][S[2]][S[3]] = 1;
        vis2[T[1]][T[2]][T[3]] = 1;
        while(!q1.empty() and !q2.empty())
        {
            date ft = q1.front();q1.pop();
            if (vis2[ft.a][ft.b][ft.c]) {printf("%d\n", ft.stp + vis2[ft.a][ft.b][ft.c]);goto End;};
            for (reg int i = 0 ; i < (signed)ve[ft.a].size() ; i ++)
            {
                for (reg int j = 0 ; j < (signed)ve[ft.b].size() ; j ++)
                {
                    if (!ok(ft.a, ft.b, ve[ft.a][i], ve[ft.b][j])) continue;
                    for (reg int k = 0 ; k < (signed)ve[ft.c].size() ; k ++)
                    {
                        if (vis1[ve[ft.a][i]][ve[ft.b][j]][ve[ft.c][k]]) continue;
                        if (!ok(ft.a, ft.c, ve[ft.a][i], ve[ft.c][k]) or !ok(ft.b, ft.c, ve[ft.b][j], ve[ft.c][k])) continue;
                        vis1[ve[ft.a][i]][ve[ft.b][j]][ve[ft.c][k]] = ft.stp + 1;
                        q1.push(((date){ve[ft.a][i], ve[ft.b][j], ve[ft.c][k], ft.stp + 1}));
                    }
                }
            }
            
            ft = q2.front();q2.pop();
            if (vis1[ft.a][ft.b][ft.c]) {printf("%d\n", ft.stp + vis1[ft.a][ft.b][ft.c]);goto End;};
            for (reg int i = 0 ; i < (signed)ve[ft.a].size() ; i ++)
            {
                for (reg int j = 0 ; j < (signed)ve[ft.b].size() ; j ++)
                {
                    if (!ok(ft.a, ft.b, ve[ft.a][i], ve[ft.b][j])) continue;
                    for (reg int k = 0 ; k < (signed)ve[ft.c].size() ; k ++)
                    {
                        if (vis2[ve[ft.a][i]][ve[ft.b][j]][ve[ft.c][k]]) continue;
                        if (!ok(ft.a, ft.c, ve[ft.a][i], ve[ft.c][k]) or !ok(ft.b, ft.c, ve[ft.b][j], ve[ft.c][k])) continue;
                        vis2[ve[ft.a][i]][ve[ft.b][j]][ve[ft.c][k]] = ft.stp + 1;
                        q2.push(((date){ve[ft.a][i], ve[ft.b][j], ve[ft.c][k], ft.stp + 1}));
                    }
                }
            }            
            
        }
        End:;
    }
    return 0;
}

📈 时间复杂度分析

• 状态总数最多为 $O(n^3)$，其中 $n \leq 180$；
• 使用双向 BFS 将搜索深度减半，极大提高效率；
• 合法剪枝避免交换、重叠等非法状态。

✅ 示例输入

5 5 2
#####
#A#B#
#   #
#b#a#
#####
0 0 0

✅ 示例输出

7