寻找最优的路测线 - 华为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, cov
    vis = [[False] * C for _ in range(R)]
    q = [(0, 0)]

    while q:
        r, c = q.pop()
        if cov[r][c] < limit:  # 信号质量不够，跳过
            continue
        vis[r][c] = True
        for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:  # 上下左右四个位置
            nr, nc = r + dr, c + dc
            if 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) >> 1
    if ok(m):
        l = m
    else:
        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];
        }
    }

    // 定义函数 ok
    auto 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;
}