(新卷,200分)- 最小传输时延Ⅱ（Java JS Python）

(新卷,200分)- 最小传输时延Ⅱ（Java & JS & Python）

题目描述

有M*N的节点矩阵，每个节点可以向8个方向（上、下、左、右及四个斜线方向）转发数据包，每个节点转发时会消耗固定时延，连续两个相同时延可以减少一个时延值（即当有K个相同时延的节点连续转发时可以减少K- 1个时延值），

求左上角（0，0）开始转发数据包到右下角（M-1，N- 1）并转发出的最短时延。

输入描述

第一行两个数字，M、N，接下来有M行，每行有N个数据，表示M* N的矩阵。

输出描述

最短时延值。

用例

题目解析

本题是求两点之间的最短路径。

对于最短路径问题，最简单的求解思路就是BFS，但是BFS只适用于处理无权图的最短路径。

所谓无权图，即图中各顶点之间的边没有权重，或者可以理解为各相连顶点之间距离相同。

对于有权图的最短路径求解，有多种解题思路，比如Dijkstra，Floyed，Bellma-ford，SPFA。

本题将使用SPFA算法来求解最短路径。

所谓SPFA算法，其实就是对无权图的BFS算法的优化。

• 在无权图的BFS扩散过程中，最先碰到终点的路径 一定是 最短路径，因为这条路径从起点到终点经历的节点数最少，而无权图中，相连节点之间的距离是相同的，因此路径中节点数越少，距离就越短。
• 在有权图中的BFS扩散过程中，最先碰到终点的路径 不一定是 最短路径，此时各节点之间的距离是不同的，因此节点数少，不能代表路径就短。

关于SPFA算法可以看下这个视频讲解：

后面有时间会补充一篇博客。

JavaScript算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { // 地图矩阵行数,列数 const [m, n] = (await readline()).split(" ").map(Number); // 地图矩阵 const matrix = []; // 最短路径矩阵，即dist[i][j]记录的是坐标(i,j)到(0,0)的最短距离 // 最短路径矩阵初始化，假设每个点到(0,0)距离无穷大 const dist = new Array(m).fill(0).map(() => new Array(n).fill(Infinity)); for (let i = 0; i < m; i++) { matrix.push((await readline()).split(" ").map(Number)); } console.log(spfa(matrix, dist, m, n)); })(); // 八个方向偏移量 const offsets = [ [-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1], ]; // 最短路径算法 function spfa(matrix, dist, m, n) { const queue = [[0, 0]]; dist[0][0] = matrix[0][0]; while (queue.length > 0) { const [x, y] = queue.shift(); for (let [offsetX, offsetY] of offsets) { const newX = x + offsetX; const newY = y + offsetY; if (newX >= 0 && newX < m && newY >= 0 && newY < n) { let newDist = dist[x][y] + matrix[newX][newY]; // 题目说：连续两个相同时延可以减少一个时延值 // 但是需要注意的是，应该不能产生负的时延值，比如前一个时延是0，当前时延也是0，则减少1个时延值，不应该变为-1 if (matrix[newX][newY] == matrix[x][y] && matrix[x][y] >= 1) { newDist -= 1; } if (newDist < dist[newX][newY]) { dist[newX][newY] = newDist; queue.push([newX, newY]); } } } } return dist[m - 1][n - 1]; }

Java算法源码

import java.util.LinkedList; import java.util.Scanner; public class Main { // 地图矩阵 static int[][] matrix; // 最短路径矩阵，即dist[i][j]记录的是坐标(i,j)到(0,0)的最短距离 static int[][] dist; // 地图矩阵行数 static int m; // 地图矩阵列数 static int n; // 八个方向偏移量 static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); m = sc.nextInt(); n = sc.nextInt(); matrix = new int[m][n]; dist = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = sc.nextInt(); // 最短路径矩阵初始化，假设每个点到(0,0)距离无穷大 dist[i][j] = Integer.MAX_VALUE; } } System.out.println(spfa()); } public static int spfa() { LinkedList<int[]> queue = new LinkedList<>(); queue.add(new int[] {0, 0}); dist[0][0] = matrix[0][0]; while (queue.size() > 0) { int[] tmp = queue.removeFirst(); int x = tmp[0], y = tmp[1]; for (int[] offset : offsets) { int newX = x + offset[0]; int newY = y + offset[1]; if (newX >= 0 && newX < m && newY >= 0 && newY < n) { int newDist = dist[x][y] + matrix[newX][newY]; // 题目说：连续两个相同时延可以减少一个时延值 // 但是需要注意的是，应该不能产生负的时延值，比如前一个时延是0，当前时延也是0，则减少1个时延值，不应该变为-1 if (matrix[newX][newY] == matrix[x][y] && matrix[newX][newY] >= 1) { newDist -= 1; } if (newDist < dist[newX][newY]) { dist[newX][newY] = newDist; queue.add(new int[] {newX, newY}); } } } } return dist[m - 1][n - 1]; } }

Python算法源码

import sys # 输入获取 m, n = map(int, input().split()) matrix = [list(map(int, input().split())) for i in range(m)] # 最短距离矩阵 dist = [[sys.maxsize for _ in range(n)] for _ in range(m)] # 八个方向的偏移量 offsets = ((-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)) # 算法入口 def spfa(): queue = [[0, 0]] dist[0][0] = matrix[0][0] while len(queue) > 0: x, y = queue.pop(0) for offsetX, offsetY in offsets: newX = x + offsetX newY = y + offsetY if m > newX >= 0 and n > newY >= 0: newDist = dist[x][y] + matrix[newX][newY] if matrix[newX][newY] == matrix[x][y] and matrix[newX][newY] >= 1: newDist -= 1 if newDist < dist[newX][newY]: dist[newX][newY] = newDist queue.append([newX, newY]) return dist[m-1][n-1] # 算法调用 print(spfa())