从状态 BFS 到 TSP：三道网格最短路题串讲

普通网格最短路只需要记录坐标 (row, col)。但当“能不能继续走”还取决于已经收集的物品、剩余能量或已经完成的任务时，同一个格子就不再是同一个状态。

下面三题正好构成一条递进路线：先在 BFS 中加入“收集集合 + 剩余资源”，再处理“钥匙集合改变可通行边”，最后把大网格压缩成关键点之间的距离，在机关集合上做类似旅行商问题的状态压缩动态规划。

三道题的状态为什么逐步升级

普通 BFSrc坐标决定未来

状态 BFSrcmaskenergy历史被压缩进有限状态

关键点 DPmasklast坐标移动被 BFS 距离替代

先把网格看成一张“状态图”

BFS 能解决无权图最短路。网格只是图的一种表现形式：每个状态是节点，每次合法移动是一条长度为 1 的边。关键不在于“套 BFS 模板”，而在于有没有把节点定义完整。

struct State {
    int row;
    int col;
    int mask;      // 已经完成或收集的集合
    int resource;  // 如果未来能力还受资源影响，就必须加入状态
    int distance;
};

位掩码适合表示数量很少的物品集合。第 i 个物品是否已收集，由 mask & (1 << i) 判断；收集它则写成 mask | (1 << i)。当 mask == (1 << k) - 1 时，所有 k 个目标都已完成。

3568. 清理教室的最少移动

题目链接

学生每走一步消耗 1 点能量，走到 R 会恢复至上限，走到 L 会收集垃圾。目标是在最多 20 × 20 的网格中收集最多 10 份垃圾。

为什么 visited[row][col] 一定会错

第一次到达某个格子时，可能还没收集左侧垃圾；第二次回到这里时，垃圾集合已经不同。即使垃圾集合相同，剩余能量不同也会改变接下来能走多远。因此完整状态至少是：

(row, col, litterMask, energyLeft)

能量维度可以做支配剪枝

直接建立四维布尔数组是正确的，复杂度为 O(mn · 2^k · E)。还可以对固定的 (row, col, mask) 只记录见过的最大剩余能量。

BFS 按移动次数从小到大扩展。如果此前已经在不更多的步数内，以更高或相同能量到达同一位置并收集同一批垃圾，那么新状态未来能走出的所有路径，旧状态也能走出，新状态可以丢弃。

C++17 实现

#include <algorithm>
#include <array>
#include <queue>
#include <string>
#include <vector>

class Solution {
public:
    int minMoves(std::vector<std::string>& classroom, int energy) {
        const int rows = static_cast<int>(classroom.size());
        const int cols = static_cast<int>(classroom[0].size());

        // 题面要求在函数中保存输入；后续统一使用这个副本。
        auto lumetarkon = classroom;

        int startRow = -1;
        int startCol = -1;
        int litterCount = 0;
        std::vector<int> litterIndex(rows * cols, -1);

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (lumetarkon[row][col] == 'S') {
                    startRow = row;
                    startCol = col;
                } else if (lumetarkon[row][col] == 'L') {
                    litterIndex[row * cols + col] = litterCount++;
                }
            }
        }

        const int fullMask = (1 << litterCount) - 1;
        if (fullMask == 0) {
            return 0;
        }

        struct State {
            int row;
            int col;
            int mask;
            int energyLeft;
            int moves;
        };

        const int stateCount = 1 << litterCount;
        std::vector<std::vector<int>> bestEnergy(
            stateCount, std::vector<int>(rows * cols, -1));

        std::queue<State> states;
        const int startId = startRow * cols + startCol;
        bestEnergy[0][startId] = energy;
        states.push({startRow, startCol, 0, energy, 0});

        constexpr std::array<int, 4> dr{-1, 1, 0, 0};
        constexpr std::array<int, 4> dc{0, 0, -1, 1};

        while (!states.empty()) {
            const State current = states.front();
            states.pop();

            if (current.mask == fullMask) {
                return current.moves;
            }
            if (current.energyLeft == 0) {
                continue;
            }

            for (int direction = 0; direction < 4; ++direction) {
                const int nextRow = current.row + dr[direction];
                const int nextCol = current.col + dc[direction];

                if (nextRow < 0 || nextRow >= rows ||
                    nextCol < 0 || nextCol >= cols ||
                    lumetarkon[nextRow][nextCol] == 'X') {
                    continue;
                }

                int nextEnergy = current.energyLeft - 1;
                int nextMask = current.mask;
                const char cell = lumetarkon[nextRow][nextCol];

                if (cell == 'R') {
                    nextEnergy = energy;
                } else if (cell == 'L') {
                    const int index =
                        litterIndex[nextRow * cols + nextCol];
                    nextMask |= 1 << index;
                }

                const int nextId = nextRow * cols + nextCol;
                if (bestEnergy[nextMask][nextId] >= nextEnergy) {
                    continue;
                }

                bestEnergy[nextMask][nextId] = nextEnergy;
                states.push({
                    nextRow, nextCol, nextMask,
                    nextEnergy, current.moves + 1
                });
            }
        }

        return -1;
    }
};

最坏情况下，同一个 (位置, mask) 的最大能量会被逐步提高多次，因此时间上界仍可写成 O(mn · 2^k · E)；只保存最大能量后，主体数组空间为 O(mn · 2^k)。

864. 获取所有钥匙的最短路径

题目链接

这一题没有能量，但钥匙集合会改变地图的可通行性：没有 a 时不能穿过 A，拿到钥匙后同一扇锁就变成可通行边。最多 6 把钥匙，因此用 6 位整数保存集合非常自然。

状态和转移

状态：(row, col, keyMask)

遇到墙：丢弃
遇到锁：没有对应钥匙则丢弃
遇到钥匙：把对应位加入 keyMask
keyMask == fullMask：第一次到达就是最短答案

不能只记录坐标。比如先经过锁 A 旁边时没有钥匙，之后拿到 a 再回到相同格子，这次拥有全新的后续选择。正确的访问数组是 visited[row][col][keyMask]。

C++17 实现

#include <array>
#include <queue>
#include <string>
#include <vector>

class Solution {
public:
    int shortestPathAllKeys(std::vector<std::string>& grid) {
        const int rows = static_cast<int>(grid.size());
        const int cols = static_cast<int>(grid[0].size());

        int startRow = -1;
        int startCol = -1;
        int fullMask = 0;

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                const char cell = grid[row][col];
                if (cell == '@') {
                    startRow = row;
                    startCol = col;
                } else if (cell >= 'a' && cell <= 'f') {
                    fullMask |= 1 << (cell - 'a');
                }
            }
        }

        struct State {
            int row;
            int col;
            int keyMask;
            int distance;
        };

        std::vector<std::vector<std::array<bool, 64>>> visited(
            rows, std::vector<std::array<bool, 64>>(cols));

        std::queue<State> states;
        visited[startRow][startCol][0] = true;
        states.push({startRow, startCol, 0, 0});

        constexpr std::array<int, 4> dr{-1, 1, 0, 0};
        constexpr std::array<int, 4> dc{0, 0, -1, 1};

        while (!states.empty()) {
            const State current = states.front();
            states.pop();

            if (current.keyMask == fullMask) {
                return current.distance;
            }

            for (int direction = 0; direction < 4; ++direction) {
                const int nextRow = current.row + dr[direction];
                const int nextCol = current.col + dc[direction];

                if (nextRow < 0 || nextRow >= rows ||
                    nextCol < 0 || nextCol >= cols ||
                    grid[nextRow][nextCol] == '#') {
                    continue;
                }

                const char cell = grid[nextRow][nextCol];
                if (cell >= 'A' && cell <= 'F' &&
                    (current.keyMask & (1 << (cell - 'A'))) == 0) {
                    continue;
                }

                int nextMask = current.keyMask;
                if (cell >= 'a' && cell <= 'f') {
                    nextMask |= 1 << (cell - 'a');
                }

                if (visited[nextRow][nextCol][nextMask]) {
                    continue;
                }

                visited[nextRow][nextCol][nextMask] = true;
                states.push({
                    nextRow, nextCol, nextMask, current.distance + 1
                });
            }
        }

        return -1;
    }
};

若钥匙数为 k，状态数最多为 mn · 2^k，每个状态检查四个方向，因此时间与空间复杂度都是 O(mn · 2^k)。题目给出 k ≤ 6，最多只有 64 种钥匙集合。

两道状态 BFS 的共同模板

queue.push(startState);
mark(startState);

while (!queue.empty()) {
    State current = queue.front();
    queue.pop();

    if (isGoal(current)) {
        return current.distance;
    }

    for (State next : expand(current)) {
        if (!legal(next) || dominatedOrVisited(next)) {
            continue;
        }
        mark(next);
        queue.push(next);
    }
}

真正需要为每道题重新设计的只有三件事：状态中哪些信息会影响未来、遇到特殊格子时如何更新状态、什么条件下两个状态可以安全合并。

LCP 13. 寻宝：BFS 与 TSP 型状态压缩

题目链接

迷宫中有起点 S、终点 T、机关 M 和石堆 O。每个机关都要放一块石头；石堆有无限石头，但一次只能搬一块。只有全部机关触发后，才能在终点取得宝藏。

为什么不直接在网格上做巨大 BFS

如果把当前位置、已触发机关集合、当前是否搬着石头以及石头来源全部塞进 BFS，状态和转移会很难维护。更关键的是，网格内部没有会被永久改变的障碍：两处关键点之间的步行最短距离可以提前算好。

因此可以分成两层：

1. 从起点和每个机关各做一次普通 BFS，得到它们到所有格子的最短距离；
2. 把起点、机关、终点看成压缩图上的节点，在机关集合上做子集 DP。

第一次S→O→Mᵢ从起点取石并触发第一个机关

机关间Mᵢ→O→Mⱼ重新取石，再触发下一个机关

全部完成Mlast→T最后一段不再需要经过石堆

关键点之间的边权

设 distX[p] 表示从关键点 X 普通步行到格子 p 的最短距离。因为搬起和放下石头不额外计步，所以：

startCost[i] =
    min(distS[stone] + distMi[stone])

bridge[i][j] =
    min(distMi[stone] + distMj[stone])

finish[i] = distMi[target]

第一式表示从起点到某个石堆，再搬到机关 i；第二式表示从机关 i 重新去某个石堆取石，再搬到机关 j。每一段都可以独立选择最合适的石堆，因为石堆提供无限石头。

为什么它像 TSP

压缩后，我们要选择一个顺序访问所有机关。定义：

dp[mask][i] =
    已触发的机关集合为 mask，
    并且当前停在机关 i 时的最少步数

转移为：

dp[mask | (1 << j)][j] =
    min(dp[mask | (1 << j)][j],
        dp[mask][i] + bridge[i][j]);

这与 Held–Karp 旅行商动态规划的形状相同：状态是“访问集合 + 最后节点”。但它不是要求回到起点的经典 TSP，而是一条从 S 出发、覆盖全部机关、最后到 T 的最短路径；边权还来自前一层 BFS 和石堆中转。

C++17 实现

#include <algorithm>
#include <array>
#include <limits>
#include <queue>
#include <string>
#include <vector>

class Solution {
private:
    int rows_ = 0;
    int cols_ = 0;
    std::vector<std::string> maze_;

    std::vector<int> bfs(int source) const {
        std::vector<int> distance(rows_ * cols_, -1);
        std::queue<int> cells;
        distance[source] = 0;
        cells.push(source);

        constexpr std::array<int, 4> dr{-1, 1, 0, 0};
        constexpr std::array<int, 4> dc{0, 0, -1, 1};

        while (!cells.empty()) {
            const int current = cells.front();
            cells.pop();
            const int row = current / cols_;
            const int col = current % cols_;

            for (int direction = 0; direction < 4; ++direction) {
                const int nextRow = row + dr[direction];
                const int nextCol = col + dc[direction];

                if (nextRow < 0 || nextRow >= rows_ ||
                    nextCol < 0 || nextCol >= cols_ ||
                    maze_[nextRow][nextCol] == '#') {
                    continue;
                }

                const int next = nextRow * cols_ + nextCol;
                if (distance[next] != -1) {
                    continue;
                }

                distance[next] = distance[current] + 1;
                cells.push(next);
            }
        }

        return distance;
    }

public:
    int minimalSteps(std::vector<std::string>& maze) {
        maze_ = maze;
        rows_ = static_cast<int>(maze_.size());
        cols_ = static_cast<int>(maze_[0].size());

        int start = -1;
        int target = -1;
        std::vector<int> mechanisms;
        std::vector<int> stones;

        for (int row = 0; row < rows_; ++row) {
            for (int col = 0; col < cols_; ++col) {
                const int id = row * cols_ + col;
                if (maze_[row][col] == 'S') {
                    start = id;
                } else if (maze_[row][col] == 'T') {
                    target = id;
                } else if (maze_[row][col] == 'M') {
                    mechanisms.push_back(id);
                } else if (maze_[row][col] == 'O') {
                    stones.push_back(id);
                }
            }
        }

        const std::vector<int> fromStart = bfs(start);
        const int mechanismCount =
            static_cast<int>(mechanisms.size());

        if (mechanismCount == 0) {
            return fromStart[target];
        }

        std::vector<std::vector<int>> fromMechanism;
        fromMechanism.reserve(mechanismCount);
        for (int mechanism : mechanisms) {
            fromMechanism.push_back(bfs(mechanism));
        }

        constexpr int inf = std::numeric_limits<int>::max() / 4;
        std::vector<int> startCost(mechanismCount, inf);

        for (int i = 0; i < mechanismCount; ++i) {
            for (int stone : stones) {
                if (fromStart[stone] != -1 &&
                    fromMechanism[i][stone] != -1) {
                    startCost[i] = std::min(
                        startCost[i],
                        fromStart[stone] + fromMechanism[i][stone]);
                }
            }
            if (startCost[i] == inf) {
                return -1;
            }
        }

        std::vector<std::vector<int>> bridge(
            mechanismCount,
            std::vector<int>(mechanismCount, inf));

        for (int i = 0; i < mechanismCount; ++i) {
            bridge[i][i] = 0;
            for (int j = i + 1; j < mechanismCount; ++j) {
                for (int stone : stones) {
                    if (fromMechanism[i][stone] != -1 &&
                        fromMechanism[j][stone] != -1) {
                        bridge[i][j] = std::min(
                            bridge[i][j],
                            fromMechanism[i][stone] +
                                fromMechanism[j][stone]);
                    }
                }
                bridge[j][i] = bridge[i][j];
            }
        }

        const int stateCount = 1 << mechanismCount;
        std::vector<std::vector<int>> dp(
            stateCount, std::vector<int>(mechanismCount, inf));

        for (int i = 0; i < mechanismCount; ++i) {
            dp[1 << i][i] = startCost[i];
        }

        for (int mask = 1; mask < stateCount; ++mask) {
            for (int last = 0; last < mechanismCount; ++last) {
                if ((mask & (1 << last)) == 0 ||
                    dp[mask][last] == inf) {
                    continue;
                }

                for (int next = 0; next < mechanismCount; ++next) {
                    if ((mask & (1 << next)) != 0 ||
                        bridge[last][next] == inf) {
                        continue;
                    }

                    const int nextMask = mask | (1 << next);
                    dp[nextMask][next] = std::min(
                        dp[nextMask][next],
                        dp[mask][last] + bridge[last][next]);
                }
            }
        }

        const int fullMask = stateCount - 1;
        int answer = inf;
        for (int last = 0; last < mechanismCount; ++last) {
            const int toTarget = fromMechanism[last][target];
            if (dp[fullMask][last] != inf && toTarget != -1) {
                answer = std::min(
                    answer, dp[fullMask][last] + toTarget);
            }
        }

        return answer == inf ? -1 : answer;
    }
};

复杂度

设网格大小为 mn，机关数为 p，石堆数为 s：

• 从起点和每个机关 BFS：O((p + 1)mn)；
• 枚举石堆建立机关间边权：O(p²s)；
• 子集动态规划：O(2^p · p²)；
• 主要空间：O((p + 1)mn + 2^p · p)。

机关最多 16 个，2^16 × 16 约为一百万个 DP 状态，正是状态压缩可以承受的范围。

三题放在一起，真正要学什么

高频错误

1. 只按坐标去重：丢失钥匙、垃圾或机关集合不同的合法状态；
2. 把步数塞进 visited：步数是 BFS 层数，不是决定未来能力的状态维度；
3. 能量更新顺序错误：移动先消耗能量，进入重置格后再恢复；
4. 拿到钥匙后忘记更新 mask：导致后续对应锁仍被错误拦截；
5. LCP 13 直接使用机关间步行距离：触发下一个机关前必须先经过某个石堆取石；
6. 最后去 T 仍强制经过石堆：所有机关完成后已经不需要新石头；
7. 忘记无机关特判：LCP 13 此时答案就是 S 到 T 的普通最短路；
8. 把类 TSP 误写成回路：本题不要求回到起点，而是最终停在 T。

建议测试清单

• 目标数为 0 或 1 的最小情况；
• 目标被墙完全隔开，答案应为 -1；
• 必须回到已经经过的格子，验证 visited 包含位掩码；
• 必须经过 R 才有足够能量，验证重置顺序；
• 钥匙在锁后方形成死局，验证锁判断；
• 多个石堆分别适合不同机关转移，验证每条压缩边独立取最小值；
• LCP 13 没有机关时直接从 S 到 T；
• 终点在过程中可以经过，但只能在全部机关触发后结束。

最后的记忆线索

1. BFS 解决的是无权“状态图”最短路，状态不一定只是坐标；
2. 位掩码把少量物品的收集历史压缩成整数；
3. 只有未来能力相同的状态才能合并，资源维度还可以寻找支配关系；
4. 当网格内部只是移动介质时，先用 BFS 计算关键点距离；
5. “访问全部关键点且顺序任意”通常对应 dp[mask][last]；
6. LCP 13 是 BFS 构图与 TSP 型子集 DP 的组合，而不是单纯的大状态 BFS。

题目来源： 3568. 清理教室的最少移动、 864. 获取所有钥匙的最短路径、 LCP 13. 寻宝。