华为OD机试：寻找最优的路测线路

题目描述

评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算。

路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示。

现给出 R 行 C 列的整数数组 Cov，每个单元格的数值 S 即为该栅格的信号质量（已归一化，无单位，值越大信号越好）。

要求从 [0, 0] 到 [R-1, C-1]设计一条最优路测路线。返回该路线得分。

规则：

1.路测路线可以上下左右四个方向，不能对角

2.路线的评分是以路线上信号最差的栅格为准的，例如路径 8→4→5→9 的值为4，该线路评分为4。线路最优表示该条线路的评分最高

输入描述

第一行表示栅格的行数 R

第二行表示栅格的列数 C

第三行开始，每一行表示栅格地图一行的信号值，如5 4 5

输出描述

最优路线的得分

备注

1 ≤ R，C ≤ 20

0 ≤ S ≤ 65535

用例

题目解析

1.首先将输入的栅格地图转换为二维数组。

2.初始化一个二维数组dp，用于记录从起点到每个栅格的最优路线得分。

3.遍历栅格地图，对于每个栅格，计算从起点到该栅格的最优路线得分，并更新dp数组。

4.最后返回dp数组中终点的值作为结果。

JS算法源码
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

let lines = [];
rl.on('line', (line) => {
  lines.push(line);
});

rl.on('close', () => {
  const r = parseInt(lines[0]);
  const c = parseInt(lines[1]);

  const matrix = lines.slice(2, 2 + r).map(line => line.split(' ').map(Number));

  const dist = Array(r * c).fill(Infinity);
  dist[0] = matrix[0][0];

  const pq = [0];

  const offsets = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  while (pq.length > 0) {
    const u = pq.pop();

    const y = u % c;
    const x = Math.floor(u / c);

    if (x === r - 1 && y === c - 1) break;

    for (let [offsetX, offsetY] of offsets) {
      const newX = x + offsetX;
      const newY = y + offsetY;

      if (newX < 0 || newX >= r || newY < 0 || newY >= c) continue;

      const v = newX * c + newY;
      const w = Math.min(dist[u], matrix[newX][newY]);

      if (dist[v] > w) {
        dist[v] = w;
        pq.push(v);
      }
    }

    pq.sort((a, b) => dist[a] - dist[b]);
  }

  console.log(dist[r * c - 1]);
});

Java算法源码
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int r = sc.nextInt();
    int c = sc.nextInt();

    int[][] matrix = new int[r][c];
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

   
    int[] dist = new int[r * c];
      dist[0] = matrix[0][0];

     PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[b] - dist[a]);
   
    pq.add(0);

  
    int[][] offsets = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    while (pq.size() > 0) {
     
      int u = pq.poll();

     
      int x = u / c;
      int y = u % c;

      
      if (x == r - 1 && y == c - 1) break;

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

         
        if (newX < 0 || newX >= r || newY < 0 || newY >= c) continue;

        
        int v = newX * c + newY;
         int w = Math.min(dist[u], matrix[newX][newY]);

          if (dist[v] < w) {
           dist[v] = w;
           pq.add(v);
        }
      }
    }

     System.out.println(dist[r * c - 1]);
  }
}

Python算法源码
 
r = int(input())
c = int(input())
matrix = [list(map(int, input().split())) for _ in range(r)]

 
def getResult():  
    dist = [0] * (r * c)   
    dist[0] = matrix[0][0]
  
    pq = [0]
      offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))

    while len(pq) > 0:
     
        u = pq.pop()
       
        x = u // c
        y = u % c

        
        if x == r - 1 and y == c - 1:
            break

       
        for offsetX, offsetY in offsets:
           
            newX = x + offsetX
            newY = y + offsetY
      
            if newX < 0 or newX >= r or newY < 0 or newY >= c:
                continue
           
            v = newX * c + newY
          
            w = min(dist[u], matrix[newX][newY])
           
            if dist[v] < w:
              
                dist[v] = w
             
                pq.append(v)
            
                pq.sort(key=lambda i: dist[i])
   
    return dist[r * c - 1]
 
print(getResult())

C算法源码
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define MAX_SIZE 400

int cmp(const void *a, const void *b) {
    return *((int *) b) - *((int *) a);
}

int main() {
    int r, c;
    scanf("%d %d", &r, &c);

    int matrix[r][c];
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    int dist[MAX_SIZE] = {0};
    dist[0] = matrix[0][0];

    int pq[MAX_SIZE] = {0};
    int pq_size = 0;

    pq[pq_size++] = 0;

    int offsets[4][2] = {{-1, 0},
                         {1,  0},
                         {0,  -1},
                         {0,  1}};

    while (pq_size > 0) {
        int u = pq[--pq_size];

        int x = u / c;
        int y = u % c;

        if (x == r - 1 && y == c - 1) break;

        for (int i = 0; i < 4; i++) {
            int newX = x + offsets[i][0];
            int newY = y + offsets[i][1];

            if (newX < 0 || newX >= r || newY < 0 || newY >= c) continue;

            int v = newX * c + newY;
            int w = (int) fmin(dist[u], matrix[newX][newY]);

            if (dist[v] < w) {
                dist[v] = w;
                pq[pq_size++] = v;
                qsort(pq, pq_size, sizeof(int), cmp);
            }
        }
    }

    printf("%d\n", dist[r * c - 1]);

    return 0;
}