网站建设工作室07flywordpress 栏目分页

网站建设工作室07fly,wordpress 栏目分页,网站建设需要的职位,安徽省建设厅执业资格注册中心网站(新卷,200分)- 最小传输时延Ⅱ#xff08;Java JS Python#xff09;题目描述有M*N的节点矩阵#xff0c;每个节点可以向8个方向#xff08;上、下、左、右及四个斜线方向#xff09;转发数据包#xff0c;每个节点转发时会消耗固定时延#xff0c;连续两个…(新卷,200分)- 最小传输时延ⅡJava JS Python题目描述有M*N的节点矩阵每个节点可以向8个方向上、下、左、右及四个斜线方向转发数据包每个节点转发时会消耗固定时延连续两个相同时延可以减少一个时延值即当有K个相同时延的节点连续转发时可以减少K- 1个时延值求左上角00开始转发数据包到右下角M-1N- 1并转发出的最短时延。输入描述第一行两个数字M、N接下来有M行每行有N个数据表示M* N的矩阵。输出描述最短时延值。用例输入3 30 2 21 2 12 2 1输出3说明无输入3 32 2 22 2 22 2 2输出4说明2 2 2 -3-1))题目解析本题是求两点之间的最短路径。对于最短路径问题最简单的求解思路就是BFS但是BFS只适用于处理无权图的最短路径。所谓无权图即图中各顶点之间的边没有权重或者可以理解为各相连顶点之间距离相同。对于有权图的最短路径求解有多种解题思路比如DijkstraFloyedBellma-fordSPFA。本题将使用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() { LinkedListint[] 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())