华为OD机试算法：最小传输时延Ⅱ

题目描述

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

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

输入描述

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

输出描述

最短时延值。

用例

题目解析

1.首先，我们需要创建一个二维数组dp，用于存储从左上角到每个位置的最短时延。dp[i][j]表示从左上角到位置(i, j)的最短时延。

2.然后，我们需要遍历输入矩阵，对于每个位置(i, j)，计算从左上角到该位置的最短时延。我们可以从上方、左方和左上方的位置转移过来，取这三个位置中最短时延加当前位置的值作为dp[i][j]的值。

3.最后，返回dp数组右下角的值，即为最短时延。

JavaScript算法源码
const readline = require("readline");
const rl = readline.createInterface({ input: process.stdin });
const iter = rl[Symbol.asyncIterator]();

async function readLine() {
  return (await iter.next()).value;
}

(async function () {
  const [m, n] = (await readLine()).split(" ").map(Number);
  const matrix = [];
  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];

        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.Scanner;

public class Main {
    // 地图矩阵
    static int[][] matrix;

    // 最短路径矩阵，即dist[i][j]记录的是坐标(i,j)到(0,0)的最短距离
    static int[][] dist;

    // 地图矩阵行数
    static int numRows;
    // 地图矩阵列数
    static int numCols;

    // 八个方向偏移量
    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);

        numRows = sc.nextInt();
        numCols = sc.nextInt();

        matrix = new int[numRows][numCols];
        dist = new int[numRows][numCols];
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                matrix[i][j] = sc.nextInt();
                // 最短路径矩阵初始化，假设每个点到(0,0)距离无穷大
                dist[i][j] = Integer.MAX_VALUE;
            }
        }

        System.out.println(spfa());
    }

    public static int spfa() {
        int[] queue = new int[numRows * numCols];
        int front = 0, rear = 0;
        queue[rear++] = 0; // 起始点入队
        dist[0][0] = matrix[0][0];

        while (front != rear) {
            int currentIndex = queue[front++];
            int currentX = currentIndex / numCols;
            int currentY = currentIndex % numCols;

            for (int[] offset : offsets) {
                int newX = currentX + offset[0];
                int newY = currentY + offset[1];

                if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols) {
                    int newDist = dist[currentX][currentY] + matrix[newX][newY];

                    // 题目说：连续两个相同时延可以减少一个时延值
                    // 但是需要注意的是，应该不能产生负的时延值，比如前一个时延是0，当前时延也是0，则减少1个时延值，不应该变为-1
                    if (matrix[newX][newY] == matrix[currentX][currentY] && matrix[newX][newY] >= 1) {
                        newDist -= 1;
                    }

                    if (newDist < dist[newX][newY]) {
                        dist[newX][newY] = newDist;
                        queue[rear++] = newX * numCols + newY; // 新点入队
                    }
                }
            }
        }

        return dist[numRows - 1][numCols - 1];
    }
}

Python算法源码
import sys
from collections import deque

# 输入获取
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 = deque()
    queue.append((0, 0))
    dist[0][0] = matrix[0][0]

    while queue:
        x, y = queue.popleft()

        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())