官方题解｜剑之试炼

题目解析

本道题目包含多个子问题，如果不加以梳理，会非常复杂，并且在梳理完毕后依然编写大量代码，并且需要特别注意实现细节，非常考验「力量」（毅力）,「智慧」与「勇气」。

预处理

由于要求必须击败所有的「波克布林」，且从地下 $i$ 层传送至地下 $i + 1$ 层须花费 $1$ 秒的时间，所以我们可以把击败波克布林需要的时间和传送的时间预处理，后面就可以把所有的「波克布林」当成同一种去处理；把此部分花费的时间记为 $\tt{cost}$。

把所有的波克布林当成「特殊点」，并将其在地图中标记为 *，接下来都可以把问题转化成：访问 $K$ 层地图上的所有特殊点需要最短时间，将其标记为 $\tt{mint}$。

那么本题的答案为 $\tt{cost + mint}$。

接下来解决如何计算 $\tt{mint}$ 的问题。

因为计算 $\tt{mint}$ 比较复杂，我们可以将其划分成若干个子问题。

第一层的初始化

对于除第一层以外的其他层，我们都可使用一样的方法进行转移，而第一层的起点固定为 $(1, 1)$，所以需要将第一层进行初始化，从 $(1, 1)$ 处执行 $BFS$，得出从第一层 $(1, 1)$ 处到达其他点的最短距离 $\tt{dist}$。

每一层的子问题

通过观察可以发现，每一次要解决的是相同的子问题，我们把每一层需要解决的问题分为以下 $5$ 步：

1. 由于得到的是上一层到达每个点的最短时间，但是在本层，这些地方有可能存在障碍物或者「波克布林」，所以需要将这些点的最短时间置为 $\infty$，得出处理后的 $\tt{dist_1}$。

2. 在 $\tt{dist_1}$ 的基础上，求出到达当层地图每个「波克布林」的位置所需要的最短时间 $\tt{dist_2}$。

3. 在 $\tt{dist_2}$ 的基础上，求出从击败当层的所有「波克布林」，并停留在任意一只「波克布林」所在的位置上需要的最短时间 $\tt{dist_3}$。

4. 在 $\tt{dist_3}$ 的基础上，将当层没有「波克布林」的位置重置为 $\infty$，得到 $\tt{dist_4}$。

5. 在 $\tt{dist_4}$ 的基础上，求出从击败当层所有「波克布林」后到达每个点需要的最短时间。

对于第 $1$ 步和第 $4$ 步比较容易实现，在此不再赘述。

对于第 $2$ 步和第 $5$ 步要解决的均为 「多源不同权的无权最短路问题」，可以使用解决 A29348.花火大会 的方法解决，但本题的地图比较小，所以对于这个子问题可以直接使用「优先队列 $BFS$」解决。

对于第 $3$ 步，要解决的是一个「哈密顿路径」问题，可以使用「状态压缩DP」解决。

状压DP 求解第 $3$ 步

首先我们需要把该层上所有「波克布林」找出并存储到 boko 中。

然后需要求解任意两个「波克布林」之间的最短路。这一步可以从每个波克布林的位置执行 $BFS$
得出。

令 $\tt{f[i][j]}$ 为该层编号为 $i$ 的「波克布林」和编号为 $j$ 的「波克布林」之间的距离。

令 $\tt{dp[i][j]}$ 表示为访问过的「波克布林」的集合为 $i$（二进制表示集合法） 时停在 $j$ 号「波克布林」处的最短时间。

那么转移方式为：$\tt{dp[i][j] = \min(dp[i][j], dp[sub_i][k] + f[k][j])}$。

其中 $sub_i$ 表示 $i$ 的包含 $k$ 但不包含 $j$ 的子集。$k$ 表示其他「波克布林」的编号。

此步完成后，我们便求出了击败当层所有的「波克布林」，并停留在任意一只「波克布里」处所需要的最短时间。

统计答案

将所有层全部处理完毕后，我们直接从处理完毕的 $\tt{dist}$ 中取最小值，即为最终的答案。

时间复杂度分析

1. 使用BFS预处理第一层的时间复杂度为 $\mathrm{O}(NM)$；
2. 解决每层子问题的第 $1$ 步和第 $4$ 步的时间复杂度为 $\mathrm{O}(NM)$；
3. 解决每层子问题的第 $2$ 步和第 $5$ 步的时间复杂度为 $\mathrm{O}(NM\log{NM})$ 或 $\mathrm{O}(NM)$；
4. 解决每层子问题的第 $3$ 步，求出任意两个「波克布林」之间的距离复杂度为 $\mathrm{O}(X_iNM)$；「状压DP」求击败当层所有「波克布林」并停留在任意一个「波克布林」处的时间复杂度为 $\mathrm{O}({X_i}^2 \cdot 2^{X_i})$。

总的时间复杂度为 $\mathrm{O}(K \cdot (X_iNM + {X_i}^2 \cdot 2^{X_i}))$。

AC代码

#include <bits/stdc++.h>

template<class T>
using Vec = std::vector<T>;
template<class T>
using VVec = Vec<Vec<T>>;

constexpr int INF = 0x3f3f3f3f;
constexpr int dirs[][2] {0, 1, 1, 0, 0, -1, -1, 0};


std::map<char, int> go;
auto init = []() {
    const std::string s = ".#RBDSG";
    constexpr int t[] {0, INF, 1, 3, 8, 24, 36};
    for (int i = 0; i < s.size(); ++i)
        go[s[i]] = t[i];
    return 0;
} ();


struct Node {
    int x, y, w;
    Node() {}
    Node(int x, int y, int w) : x(x), y(y), w(w) {}
    bool operator > (const Node &other) const {
        return w > other.w;
    }
};

VVec<int> bfs(const Vec<std::string> &grid, int sx, int sy, const std::string &block = "") {
    int n = grid.size(), m = grid[0].size();
    VVec<int> dist(n, Vec<int>(m, INF));
    dist[sx][sy] = 0;
    std::queue<std::pair<int, int>> q;
    q.emplace(sx, sy);
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (auto &[dx, dy] : dirs) {
            int nx = x + dx, ny = y + dy;
            if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
            if (block.find(grid[nx][ny]) != std::string::npos) continue;
            if (dist[nx][ny] < INF) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.emplace(nx, ny);
        }
    }
    return dist;
}

void cover(VVec<int> &dist, const Vec<std::string> &grid, const std::string &block = "") {
    int n = grid.size(), m = grid[0].size();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (block.find(grid[i][j]) != std::string::npos)
                dist[i][j] = INF;
}

void getMinDist(VVec<int> &dist, const Vec<std::string> &grid, const std::string &block = "") {
    int n = grid.size(), m = grid[0].size();
    std::priority_queue<Node, Vec<Node>, std::greater<Node>> pq;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            pq.emplace(i, j, dist[i][j]);
    while (!pq.empty()) {
        auto [x, y, w] = pq.top(); pq.pop();
        if (dist[x][y] < w) continue;
        for (auto &[dx, dy] : dirs) {
            int nx = x + dx, ny = y + dy;
            if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
            if (block.find(grid[nx][ny]) != std::string::npos) continue;
            if (dist[nx][ny] <= w + 1) continue;
            dist[nx][ny] = w + 1;
            pq.emplace(nx, ny, w + 1);
        }
    }
}

void hamilton(VVec<int> &dist, const Vec<std::string> &grid) {
    int n = grid.size(), m = grid[0].size();
    Vec<std::pair<int, int>> boko;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (grid[i][j] == '*')
                boko.emplace_back(i, j);
    int sz = boko.size();
    VVec<int> f(sz);
    for (int i = 0; i < sz; ++i) {
        const auto &[sx, sy] = boko[i];
        auto toOther = bfs(grid, sx, sy, "#");
        for (auto &[x, y] : boko)
            f[i].emplace_back(toOther[x][y]);
    }
    VVec<int> dp(1 << sz, Vec<int>(sz, INF));
    for (int i = 0; i < sz; ++i) {
        const auto &[x, y] = boko[i];
        dp[1 << i][i] = dist[x][y];
    }
    for (int i = 0; i < (1 << sz); ++i) {
        for (int j = 0; j < sz; ++j) {
            if (~i >> j & 1) continue;
            for (int k = 0; k < sz; ++k) {
                if (~(i ^ 1 << j) >> k & 1) continue;
                dp[i][j] = std::min(dp[i][j], dp[i ^ 1 << j][k] + f[k][j]);
            }
        }
    }
    for (int i = 0; i < sz; ++i) {
        const auto &[x, y] = boko[i];
        dist[x][y] = dp[(1 << sz) - 1][i];
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, k;
    std::cin >> n >> m >> k;
    VVec<std::string> grids(k, Vec<std::string>(n));
    for (auto &grid : grids)
        for (auto &row : grid)
            std::cin >> row;
    int cost = k - 1;
    for (auto &grid : grids) for (auto &row : grid)
        for (auto &ch : row)
            if (ch != '#' and ch != '.') {
                cost += go[ch];
                ch = '*';
            }
    VVec<int> dist = bfs(grids[0], 0, 0, "#*");
    for (auto &grid : grids) {
        cover(dist, grid, "#*");
        getMinDist(dist, grid, "#");
        hamilton(dist, grid);
        cover(dist, grid, "#.");
        getMinDist(dist, grid, "#");
    }
    int mint = INF;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            mint = std::min(mint, dist[i][j]);
    std::cout << mint + cost << '\n';
    return 0;
}