寻找最优的路测线 - 华为OD统一考试

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

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

路测的时候，希望选择一条信号最好的路线(彼此相连的栅格集合)进行演示。现给出 R 行 C 列的整数数组 Cov ,每个单元格的数值 S 即为该栅格的信号质量(已归一化，无单位,值越大信号越好)。

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

规则：

路测路线可以上下左右四个方向，不能对角。
路线的评分是以路线上信号最差的栅格为准的。例如路径 8→4→5→9 的值为 4 ，该线路评分为 4 。线路最优表示该条线路的评分最高。

输入描述

第一行表示栅格的行数 R；

第二行表示栅格的列数 C；

第三行开始，每一行表示栅格地图一行的信号值，每个单元格的数值为 S 。

1≤R,C≤20
1≤S≤65535

输出描述

最优路线的得分。

示例1

输入：
3
3
5 4 5
1 2 6
7 4 6输出：
4说明：
路线为： 5→4→5→6→6 。

示例2

输入：
6
5
3 4 6 3 4
0 2 1 1 7
8 8 3 2 7
3 2 4 9 8
4 1 2 0 0
4 6 5 4 3输出：
3说明：
路线为： 3→4→6→3→4→7→7→8→9→4→3→8→8→3→4→4→6→5→4→3 。

题解

该题目属于搜索算法的一种，通过搜索找到最优路径。首先，对于每个栅格，其数值 S 表示信号质量。我们需要从栅格 [0,0] 出发，沿着上下左右四个方向，选择信号最优的路径到达 [R-1,C-1]。

为了找到最优路径，可以采用二分搜索的方式，不断调整路径信号的评分限制，直到找到最优路径。在搜索路径的过程中，需要使用队列或栈等数据结构来保存当前搜索的状态。

Java

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;/*** @author code5bug*/
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int R = scanner.nextInt(), C = scanner.nextInt();int[][] cov = new int[R][C];for (int i = 0; i < R; i++) {for (int j = 0; j < C; j++) {cov[i][j] = scanner.nextInt();}}int l = 1, r = 65535 + 1;while (l + 1 < r) {int m = (l + r) >> 1;if (ok(R, C, cov, m)) {l = m;} else {r = m;}}System.out.println(l);}// 条线路的评分 limit 能否从 (0,0) 到达 (R-1, C-1)private static boolean ok(int R, int C, int[][] cov, int limit) {boolean[][] vis = new boolean[R][C];int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 初始化队列，起点为 (0, 0)Queue<int[]> queue = new ArrayDeque<>();queue.offer(new int[]{0, 0});while (!queue.isEmpty()) {int[] current = queue.poll();int r = current[0], c = current[1];if (cov[r][c] < limit) continue;   // 信号质量不够，跳过vis[r][c] = true;// 遍历四个方向for (int[] direction : directions) {int nr = r + direction[0], nc = c + direction[1];if (0 <= nr && nr < R && 0 <= nc && nc < C && !vis[nr][nc]) {queue.offer(new int[]{nr, nc});}}}return vis[R - 1][C - 1];}
}

Python

R, C = int(input()), int(input())
cov = [list(map(int, input().split())) for _ in range(R)]def ok(limit: int) -> bool:""" 条线路的评分 limit 能否从 (0,0) 到达 (R-1, C-1) """global R, C, covvis = [[False] * C for _ in range(R)]q = [(0, 0)]while q:r, c = q.pop()if cov[r][c] < limit:  # 信号质量不够，跳过continuevis[r][c] = Truefor dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:  # 上下左右四个位置nr, nc = r + dr, c + dcif 0 <= nr < R and 0 <= nc < C and not vis[nr][nc]:q.append((nr, nc))return vis[R-1][C-1]l, r = 1, 65535 + 1
while l + 1 < r:m = (l + r) >> 1if ok(m):l = melse:r = m
print(l)

C++

#include <iostream>
#include <vector>
#include <stack>using namespace std;int main() {int R, C;cin >> R >> C;// 读取输入矩阵vector<vector<int>> cov(R, vector<int>(C));for (int i = 0; i < R; ++i) {for (int j = 0; j < C; ++j) {cin >> cov[i][j];}}// 定义函数 okauto ok = [&](int limit) -> bool {vector<vector<bool>> vis(R, vector<bool>(C, false));stack<pair<int, int>> q;q.push({0, 0});while (!q.empty()) {int r = q.top().first;int c = q.top().second;q.pop();if (cov[r][c] < limit) {continue;  // 信号质量不够，跳过}vis[r][c] = true;// 遍历四个方向vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};for (const auto& direction : directions) {int nr = r + direction.first;int nc = c + direction.second;if (0 <= nr && nr < R && 0 <= nc && nc < C && !vis[nr][nc]) {q.push({nr, nc});}}}return vis[R-1][C-1];};// 二分搜索int l = 1, r = 65535 + 1;while (l + 1 < r) {int m = (l + r) >> 1;if (ok(m)) {l = m;} else {r = m;}}cout << l << endl;return 0;
}