题面描述

在一个 $M \times N$ 的网格中，每个单元格代表不同的能量强度，其中灰色单元格为禁地，橙色单元格为能量覆盖区域，绿色单元格为生命之树，表示生命之树散发的初始能量强度。能量强度会向外传播，每向外一格减少 $1$，最低为 $0$。若某位置接收到多棵生命之树的能量，取最大值。如果能量强度低于阈值 $Th$，则能量中断。任务是从左上角到右下角寻找一条信号不中断的最短路径，若不存在则返回 $0$。

思路：Dijkstra算法，最短路

容易这个问题可以分成两部分求解： 第一步：求解网格内每个点的最大信号强度。 第二步：对最大信号强度大于等于 $Th$，且相邻的点对连边，最后输出出发点到终点的最短路。

对于第一步，我们可以先建一个图，把网格上的每一个点映射到图上的点，并在图上创建一个虚拟的源点，对于每个网格图上的点，当它的信号强度为 $W$ 时, 从源点到网格图上的点连一条边权为 $-W$ 的边。

然后对于每个在网格图上相邻的节点，我们在它们之间连一条边权为 $1$ 的边，此时虚拟源点到每个网格图上的点的最短路即为负的最大信号强度，因为容易发现我们只是把操作反着进行了。

对于第二步，我们通过 $BFS$，求解出发点到终点的最短路，注意特判出发点不合法的情况。

题解

这个问题可以分为两个主要部分进行求解：

1. 计算每个网格点的最大信号强度：

   • 我们可以构建一个图，将网格中的每个点映射为图上的点，并创建一个虚拟源点。对于每个网格点，当其信号强度为 $W$ 时，从源点到该网格点连一条权重为 $-W$ 的边。这样，当我们进行最短路径计算时，实际得到的是每个点的最大信号强度的负值。
   • 此外，对于相邻的网格点（上下左右），我们在它们之间连一条权重为 $1$ 的边。这样，每个网格点的最短路径即为负的最大信号强度。

2. 寻找从起点到终点的最短路径：

   • 在确定了每个点的最大信号强度后，我们需要判断哪些点的信号强度大于等于给定的阈值 $Th$，并在这些点之间建立边。最后，使用广度优先搜索（BFS）算法，计算从起点到终点的最短路径。

代码

cpp

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

int grid[1005][1005]; // 存储网格信号强度的数组
int th, n, m; // 阈值，网格的行数和列数
vector<int> d{-1, 0, 1, 0, -1}; // 方向数组，用于快速计算相邻节点的坐标

// 自定义比较器，用于优先队列，按边权大小排序
struct Compare {
    bool operator()(const vector<int>& a, const vector<int>& b) {
        return a[0] > b[0]; // 边权较大的排在后面
    }
};

// BFS求解函数，返回从起点到终点的最短路径
int solve(queue<vector<int>> q2) {
    int dis = 0; // 记录当前的距离
    while (!q2.empty()) {
        int siz = q2.size(); // 当前队列大小
        
        for (int i = 1; i <= siz; i++) {
            vector<int> tp = q2.front(); // 获取队头元素
            q2.pop(); // 弹出队头元素
            
            // 如果到达终点，返回当前距离
            if (tp[0] == n - 1 && tp[1] == m - 1) {
                return dis;
            }
            
            // 遍历四个方向
            for (int j = 1; j <= 4; j++) {
                int tx = tp[0] + d[j - 1]; // 新行坐标
                int ty = tp[1] + d[j]; // 新列坐标
                
                // 检查边界及信号强度是否符合条件
                if (tx >= 0 && ty >= 0 && tx < n && ty < m && grid[tx][ty] >= th) {
                    grid[tx][ty] = 0; // 将信号强度置为0，作为访问标记
                    q2.push({tx, ty}); // 将新坐标入队
                }
            }
        }
        dis++; // 增加距离
    }
    
    return 0; // 没有有效路径，返回0
}

int main() {
    cin >> th >> n >> m; // 输入阈值、行数和列数
    int k; // 生命之树的个数
    cin >> k;
    
    // 处理每棵生命之树的信息
    for (int i = 0; i < k; i++) {
        int x, y, w; // 生命之树的坐标和初始能量强度
        cin >> x >> y >> w;
        grid[x][y] = -w; // 将生命之树的初始能量变为负值
    }
    
    priority_queue<vector<int>, vector<vector<int>>, Compare> q; // 优先队列用于Dijkstra算法
    
    // 初始化优先队列，计算从源点到每个点的最短路径
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            q.push({grid[i][j], i, j}); // 将每个点的信号强度及坐标入队
        }
    }
    
    while (!q.empty()) {
        vector<int> tp = q.top(); // 获取队顶元素
        q.pop(); // 弹出队顶元素
        
        // 如果该节点的值已经被松弛过，跳过
        if (grid[tp[1]][tp[2]] != tp[0]) continue;
        
        // 遍历四个方向进行松弛操作
        for (int i = 1; i <= 4; i++) {
            int tx = tp[1] + d[i - 1]; // 新行坐标
            int ty = tp[2] + d[i]; // 新列坐标
            
            // 检查边界
            if (tx >= 0 && ty >= 0 && tx < n && ty < m) {
                // 如果新计算的路径更优，更新信号强度并入队
                if (grid[tx][ty] > tp[0] + 1) {
                    grid[tx][ty] = tp[0] + 1;
                    q.push({tp[0] + 1, tx, ty});
                }
            }
        }
    }
    
    // 将信号强度转换回题目要求的格式
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            grid[i][j] = max(0, -grid[i][j]); // 重新计算信号强度
        }
    }
    
    // 对信号强度大于等于 Th 的点进行BFS，寻找路径
    queue<vector<int>> q2;
    if (grid[0][0] < th) { // 特判出发点是否合法
        cout << 0 << endl; // 如果出发点信号强度不够，输出0
        return 0;
    }
    
    q2.push({0, 0}); // 将出发点入队
    grid[0][0] = 0; // 标记为已访问
    int dis = 0; // 距离初始化
    
    cout << solve(q2) << endl; // 调用BFS求解并输出结果
    
    return 0;
}

题目描述

在游戏世界中，给定一个 $M$ * $N$ 的网格，其中每个单元格都填有数字，数字大小表示覆盖能量强度。灰色网格代表禁地，橙色网格代表能量覆盖区域，绿色网格代表生命之树，绿色网格内数字大小表示该生命之树散发的能量的初始强度。 已知每个网格内的能量强度每向外(上下左右)传播一格，能量强度减 $1$，最小减为 $0$ 。

0表示无信号，如下图示。当某个位置可以同时接收到多棵生命之树的能量时，取其中接收能量强度的最大值作为该位置的能量强度，对于给定网格，请判断是否存在一条路径，使得从左上角移动到右下角过程中能量不中断，只能上下左右移动。假设接吸收的能量强度低于门限 $Th$ ，能量就会中断。

注意:出发点固定在网格的左上角，终点是网格的右下角。

输入

第一行输入能量强度 $Th$ 。( $1 \le Th \le 100$)

第二行输入矩阵 $M$ 、$N$ 。($1 \le M \le 100，1\le N \le100$)

第三行输入生命之树的个数 $K$。 ($1 \le K \le 100$)

后续 $K$ 行输入生命之树的位置及初始能量强度。(前两个值表示生命之树所在行、列索引，第 $3$ 个值表示生命之树初始能量强度)

输出

返回信号不中断的最短路径，不存在返回 $0$。

样例1

输入

1
4 4
2
0 1 2
3 2 3

输出

6

说明

1. 能量强度门限 $Th$ = $1$

2. $M$ = $4$,$N$ = $4$

3. $4$ * $4$ 网格中一共包含 $2$ 棵生命之树

4. $2$ 棵生命之树的位置，其中第 $1$ 个生命之树在第 $0$ 行第 $1$ 列、初始能量强度 = $2$ ；第 $2$ 棵生命之树在第 $3$ 行第 $2$ 列、初始能量强度 = $3$

样例2

输入

1
5 5
5
0 1 2
0 4 3
2 3 2
4 0 3
4 3 2

输出

8

说明

1. 能量强度门限 $Th$ = $1$
2. $M$ = $5$ , $N$ = $5$
3. $5$ * $5$ 网格中一共包含 $5$ 棵生命之树
4. $5$ 棵生命之树的位置，其中第 $1$ 棵生命之树在第 $0$ 行第 $1$ 列、初始能量强度 = $2$:第 $2$ 棵生命之树在第 $0$ 行第 $4$列、初始能量强度 =$3$;第 $3$ 棵生命之树在第 $2$ 行第 $3$ 列、初始能量强度 = $2$ ;第 $4$ 棵生命之树在第 $4$ 行第 $0$ 列 、初始能量强度 $3$ ;第 $5$ 棵生命之树在第 $4$ 行第 $3$ 列、初始能量强度= $2$;

注：如上Grid ，绿色表示生命之树，橙色为生命之树散发的能量往外传播后覆盖的区域，按照途中箭头方向移动路径最短。