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

题目描述

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

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

输入描述

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

输出描述

最短时延值。

用例

输入	3 3 0 2 2 1 2 1 2 2 1
输出	3
说明	无

输入	3 3 2 2 2 2 2 2 2 2 2
输出	4
说明	（2 + 2 + 2 -（3-1))

题目解析

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

对于最短路径问题，最简单的求解思路就是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())