剑之试炼｜状压DP与多源最短路

第六题 - 剑之试炼

题目链接跳转：点击跳转

这道题超级恶心，我发自内心地对那些在比赛过程中 AC 此题目的同学表示尊敬。

思路上非常好想，由于所有的怪兽都要打，且打每一个怪兽的时间都是固定的，因此我们可以在一开始就先预处理出打完所有怪兽的时间，需要优化的就只有赶路的时间了。

先考虑每一层的情况，对于任意一层来说，关键点就是找到一个最优的路径（从某一个起点出发，经过所有的点后再传送到下一层的最短路径）即可。学习过状态压缩动态规划的同学可以很容易想到模板题【最短 Hamilton 路径】（洛谷链接：链接跳转）。

对于每一层来说，具体的实现方法和函数如下：

1. cover(dist, grid, "#*");

   • 将dist和grid中标记为"#"或"*"的所有障碍物进行覆盖处理。这一步的作用是标记出所有不可通行的区域，为后续的距离计算或路径规划提供基础。

2. getMinDist(dist, grid, "#");

   • 计算从当前所在位置到grid中标记为"#"（障碍物）位置的最短距离。这一步的作用是为后续的路径规划获取到障碍物的距离信息，方便下一步进行路径选择。

3. hamilton(dist, grid);

   • 在dist和grid上执行哈密顿路径（Hamiltonian Path）的计算，目的是找到一条经过所有目标点的路径。这一步的作用是根据前面的距离信息，找到一条经过所有必经点的路径。

4. cover(dist, grid, "#.");

   • 对dist和grid中标记为"#"（障碍物）和"."（空地）的部分进行覆盖处理。这一步是为了确保后续的距离计算排除已标记的障碍物，并识别可通行的路径。

5. getMinDist(dist, grid, "#");

   • 再次计算从当前所在位置到grid中标记为"#"的最短距离。这一步是为了更新经过路径覆盖处理后的最短距离，确保得到最新的距离信息。

除此之外就是一些小的细节优化了，具体请参阅代码注释。

本题的 AC 代码如下（本代码参考了黄老师的 std，并加以修改（我是不会说我数组传来传去把自己传死了，讨厌指针的一天）），若需要更详细的解答，可以 参考本文：

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

int n, m, k;
string map[30][105];
int dist[105][105];
struct node{
    int x, y, w;
    bool friend operator < (node a, node b){
        return a.w > b.w;
    }
};
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

/*
PS：本来想用纯数组加指针的方式做的。
后来写着写着把自己写死掉了，还是 vector 方便。
普通的二维数组传来传去简直要我的命。
::: 虽然我的编译器见不得 c++11 的标准，每次都给我提 warning。头大。
*/

// 转换，将每一个怪兽的血量都转换成对应的数字。
int calc(char c){
    if (c == '.') return 0;
    if (c == 'R') return 1;
    if (c == 'B') return 3;
    if (c == 'D') return 8;
    if (c == 'S') return 24;
    if (c == 'G') return 36;
    return 0x7f7f7f7f;
}

// 最普通的广度优先搜索算法：
// 记录从 sx, sy 出发，到当前层 grid 的每一个点的最短路径。
// 其中 block 代表无法走的格子。
vector<vector<int> > bfs(vector<string> &grid, int sx, int sy, string block){
    vector<vector<int> > dist(n, vector<int>(m, 0x7f7f7f7f));
    dist[sx][sy] = 0;
    struct node{
        int x, y;
    }; queue<node> que;
    que.push((node){sx, sy});
    while(!que.empty()){
        node t = que.front();
        que.pop();
        for (int i=0; i<4; i++){
            int cx = t.x + dx[i];
            int cy = t.y + dy[i];
            if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;
            // 字符串函数，判断当前格子是否是障碍物，如果是障碍物的话就忽略。
            if (block.find(grid[cx][cy]) != string::npos) continue;
            if (dist[cx][cy] < 0x7f7f7f7f) continue;
            dist[cx][cy] = dist[t.x][t.y] + 1;
            que.push((node){cx, cy});
        }
    }
    return dist;
}

// 将 dist 数组根据 grid 复原。
// 如果当前位置无法被走到，则将 dist 更新为无穷大。
void cover(vector<vector<int> > &dist, vector<string> &grid, string block){
    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] = 0x7f7f7f7f;
        }
    }
    return ;
}

// dijkstra 最短路算法。
// 主要作用是计算并更新每个节点到其余节点的最短距离，并通过广度优先搜索（BFS）算法来实现。
// dist[i][j] 是从一开始设定的起点到达 (i, j) 的累积代价，考虑了路径上经过的每个格子的代价。
void getMinDist(vector<vector<int> > &dist, vector<string> &grid, string block){
    priority_queue<node> que;
    // 一开始把所有起点都入队。
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            que.push((node){i, j, dist[i][j]});
        }
    }

    while(!que.empty()){
        node t = que.top();
        que.pop();
        if (dist[t.x][t.y] < t.w) continue;
        for (int i=0; i<4; i++){
            int cx = t.x + dx[i];
            int cy = t.y + dy[i];
            if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;
            if (block.find(grid[cx][cy]) != string::npos) continue;
            // 如果已经存在更优解了，就忽略。
            if (dist[cx][cy] <= t.w + 1) continue;
            dist[cx][cy] = t.w + 1;
            que.push((node){cx, cy, t.w + 1});
        }
    }
}

// 计算汉密尔顿路径
// 即从起点出发走完所有的点最后再回来的路径最短路。
void hamilton(vector<vector<int> > &dist, vector<string> &grid){
    struct node{
        int x, y;
    }; vector<node> vec;
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            if (grid[i][j] == '*')
                vec.push_back((node){i, j});
        }
    }

    int k = vec.size();
    vector<vector<int> > f(k);
    // f 数组用于计算每一个关键节点（怪兽）之间的最短路。
    for (int i=0; i<k; i++){
        int sx = vec[i].x;
        int sy = vec[i].y;
        auto toOther = bfs(grid, sx, sy, "#");
        for (int j=0; j<k; j++){
            f[i].push_back(toOther[vec[j].x][vec[j].y]);
        }
    }

    // 对于 Hamilton 路径不熟悉的，直接去搜洛谷模板题先看一眼。
    // X04-01 的同学应该是学过的（毕竟是我挑的题目）。
    vector<vector<int> > dp(1 << k, vector<int>(k, 0x7f7f7f7f));
    for (int i=0; i<k; i++){
        int sx = vec[i].x;
        int sy = vec[i].y;
        dp[1 << i][i] = dist[sx][sy];
    }
    for (int i=0; i<(1<<k); i++){
        for (int j=0; j<k; j++){
            if (~i >> j & 1) continue;
            for (int l=0; l<k; l++){
                if (~(i ^ 1 << j) >> l & 1) continue;
                dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][l] + f[l][j]);
            }
        }
    }
    for (int i=0; i<k; i++){
        int sx = vec[i].x;
        int sy = vec[i].y;
        dist[sx][sy] = dp[(1 << k) - 1][i];
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    vector<vector<string> > grids(k, vector<string>(n));
    for (auto &grid : grids){
        for (auto &row : grid){
            cin >>  row;
        }
    }
    int cost = k - 1;
    for (auto &grid : grids){
        for (auto &row : grid){
            for (auto &c : row){
                if (c != '#' && c != '.'){
                    cost += calc(c);
                    c = '*';
                }
            }
        }
    }

    vector<vector<int> > dist = bfs(grids[0], 0, 0, "#*");
    
    /*
        先排除掉某些障碍物和关键点，以计算初步的最短路径。
        再使用 hamilton 函数来处理关键点之间的路径规划，得到所有关键点的最优路径。
        最后进一步排除空白区域和障碍物，重新计算网格中各点之间的最短路径，得到最终结果。
    */
    for (auto &grid : grids){
        cover(dist, grid, "#*");
        getMinDist(dist, grid, "#");
        hamilton(dist, grid);
        cover(dist, grid, "#.");
        getMinDist(dist, grid, "#");
    }

    // 计算答案。
    int ans = 0x7f7f7f7f;
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            ans = min(ans, dist[i][j]);
        }
    }

    cout << ans + cost << endl;
    return 0;
}