2023.12.20-秋招-第二题-通话不中断的最短路径

螭吻嘲风 LV 5 @ 7 months ago

只用BFS的解法。第一步是根据生命之树的位置，计算出网格内部每个节点的最大信号强度。思路就是从每颗生命之树作为起点进行BFS来更新网格中信号强度。在BFS过程中，如果碰到节点的能量大于等于该生命之树到此位置的能量，就可以剪枝返回了。第二步还是用BFS计算从左上节点到右下节点的最短路径，BFS剪枝的条件是碰到节点能量小于Th。

#include <bits/stdc++.h>
#include <unordered_map>
#include <vector>
using namespace std;

int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int Th, m, n;

void update_graph(vector<vector<int>> &map_graph, int x, int y, int e) {
    if(map_graph[x][y] >= e)
        return;
    queue<pair<int, int>> q;
    q.emplace(x, y);
    int qz = q.size();
    while(!q.empty()) {
        for(int i=0; i<qz; ++i) {
            auto cur = q.front();
            q.pop();
            int cx = cur.first, cy = cur.second;
            if(e <= map_graph[cx][cy])
                continue;
            map_graph[cx][cy] = e;
            for(int j=0; j<4; ++j) {
                int nx = cx+dir[j][0];
                int ny = cy+dir[j][1];
                if(nx >=0 && nx <m && ny >=0 && ny < n) {
                    q.emplace(nx, ny);
                }
            }
        }
        --e;
        qz = q.size();
    }
    return;
}

int bfs(vector<vector<int>> &map_graph) {
    queue<pair<int, int>> q;
    vector<vector<bool>> vis(m, vector<bool>(n));
    q.emplace(0, 0);
    int qz = 1;
    int len = 0;
    vis[0][0] = true;
    while(!q.empty()) {
        for(int i=0; i<qz; ++i) {
            auto cur = q.front();
            q.pop();
            int cx = cur.first, cy = cur.second;
            if(map_graph[cx][cy] < Th)
                continue;
            if(cx == m-1 && cy == n-1) {
                return len;
            }
            for(int j=0; j<4; ++j) {
                int nx = cx+dir[j][0];
                int ny = cy+dir[j][1];
                if(nx >=0 && nx <m && ny >=0 && ny < n && vis[nx][ny] == false) {
                    q.emplace(nx, ny);
                    vis[nx][ny] = true;
                }
            }
        }
        qz = q.size();
        ++len;
    }
    return -1;
}

int main() {
    int tn, row, col, val;
    cin >> Th >> m >> n;
    cin >> tn;
    vector<vector<int>> map_graph(m, vector<int>(n));
    for(int i=0; i<tn; ++i) {
        cin >> row >> col >> val;
        update_graph(map_graph, row, col, val);
    }
    int ret = bfs(map_graph);
    if(ret >= 0)
        printf("%d\n", ret);
    else
        printf("0\n");
    return 0;
}

TaZi SU @ 9 months ago

题面描述

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

思路：Dijkstra算法，最短路

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

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

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

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

题解

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

计算每个网格点的最大信号强度：
- 我们可以构建一个图，将网格中的每个点映射为图上的点，并创建一个虚拟源点。对于每个网格点，当其信号强度为 $W$ 时，从源点到该网格点连一条权重为 $-W$ 的边。这样，当我们进行最短路径计算时，实际得到的是每个点的最大信号强度的负值。
- 此外，对于相邻的网格点（上下左右），我们在它们之间连一条权重为 $1$ 的边。这样，每个网格点的最短路径即为负的最大信号强度。
寻找从起点到终点的最短路径：
- 在确定了每个点的最大信号强度后，我们需要判断哪些点的信号强度大于等于给定的阈值 $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;
}

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

数据结构

# Submissions

100

Accepted

Uploaded By

TaZi

2 solutions

题面描述

思路：Dijkstra算法，最短路

题解

代码

cpp

Information

Status

Development

Support