【华为OD-E卷 - 89 计算网络信号 100分（python、java、c++、js、c）】

25-03-07 19:41

2909

6627

blog.csdn.net

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷 - 计算网络信号 100分（python、java、c++、js、c）】

题目

网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物。
array[m][n] 的二维数组代表网格地图， array[i][j] = 0代表i行j列是空旷位置; array[i][j] = x(x为正整数)代表i行j列是信号源，信号强度是x; array[i][j] = -1代表i行j列是阻隔物。信号源只有1个，阻隔物可能有0个或多个网络信号衰减是上下左右相邻的网格衰减1 现要求输出对应位置的网络信号值。

输入描述

输入为三行，

第一行为 m 、n ，代表输入是一个 m × n 的数组。第二行是一串 m × n 个用空格分隔的整数。每连续 n 个数代表一行，再往后 n 个代表下一行，以此类推。对应的值代表对应的网格是空旷位置，还是信号源，还是阻隔物。第三行是 i 、 j，代表需要计算array[i][j]的网络信号值。注意：此处 i 和 j 均从 0 开始，即第一行 i 为 0。

例如

6 5 0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 1 4 代表如下地图
在这里插入图片描述
需要输出第1行第4列的网络信号值，如下图，值为2。

输出描述

输出对应位置的网络信号值，如果网络信号未覆盖到，也输出0。

一个网格如果可以途径不同的传播衰减路径传达，取较大的值作为其信号值

用例

用例一：

输入：

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2
3

输出：

2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例二：

输入：

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2
3

输出：

0
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

python解法

解题思路：

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

java解法

解题思路
问题描述
给定一个二维网格，每个位置可能为以下几种情况：

0 表示无信号覆盖区域。
正整数表示信号源，数值越大，信号越强。
信号可以向上下左右传播，且每传播一步信号减弱 1。传播到信号值为 0 时停止。需要确定目标位置的信号强度。

算法设计
使用广度优先搜索（BFS）算法模拟信号传播的过程：

遍历网格，找到所有信号源，将其加入 BFS 队列。
从队列中取出信号源，向其上下左右的方向传播信号，直到信号减弱为 0。
最终得到目标位置的信号强度。
输入输出格式

输入：网格大小 m x n，信号源及其强度，以及目标位置的坐标。
输出：目标位置的信号强度。

import java.util.*;

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

        // 读取网格的行数和列数
        int m = input.nextInt();
        int n = input.nextInt();

        // 初始化网格
        int[][] grid = new int[m][n];

        // BFS 队列，用于处理信号传播
        Queue<int[]> queue = new LinkedList<>();

        // 定义信号源的初始坐标
        int signalX = -1, signalY = -1;

        // 读取网格数据，找到所有信号源并将其加入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = input.nextInt();
                if (grid[i][j] > 0) { // 发现信号源
                    signalX = i;
                    signalY = j;
                    queue.offer(new int[]{i, j, grid[i][j]}); // 将信号源加入队列
                }
            }
        }

        // 读取目标位置
        int targetX = input.nextInt();
        int targetY = input.nextInt();

        // 调用 BFS 方法，计算目标位置的信号强度
        System.out.println(bfs(grid, m, n, queue, targetX, targetY));
    }

    /**
     * 广度优先搜索 (BFS) 计算目标位置的信号强度
     * 
     * @param grid 网格表示信号传播区域
     * @param m 网格的行数
     * @param n 网格的列数
     * @param queue 信号源队列
     * @param targetX 目标位置的行坐标
     * @param targetY 目标位置的列坐标
     * @return 目标位置的信号强度
     */
    public static int bfs(int[][] grid, int m, int n, Queue<int[]> queue, int targetX, int targetY) {
        // 定义四个方向的移动向量（上、下、左、右）
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 开始 BFS 遍历
        while (!queue.isEmpty()) {
            // 从队列中取出当前信号源
            int[] current = queue.poll();
            int x = current[0], y = current[1], signal = current[2];

            // 遍历四个方向
            for (int[] dir : directions) {
                int newX = x + dir[0]; // 新的行坐标
                int newY = y + dir[1]; // 新的列坐标

                // 检查新位置是否在网格范围内且未被覆盖
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 0) {
                    // 更新新位置的信号强度
                    grid[newX][newY] = signal - 1;

                    // 如果信号强度仍大于 0，则将其加入队列继续传播
                    if (signal - 1 > 0) {
                        queue.offer(new int[]{newX, newY, signal - 1});
                    }
                }
            }
        }

        // 返回目标位置的信号强度
        return grid[targetX][targetY];
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

解题思路

使用广度优先搜索（BFS）模拟信号传播：
找到所有信号源，初始化 BFS 队列。
从信号源开始，依次向上下左右传播信号，更新网格中各位置的信号强度。
如果信号传播到目标位置 (tx, ty)，记录其信号值。
由于 BFS 会按照距离由近及远的顺序进行遍历，保证每个位置的信号强度为其最强值。

#include 
#include 
#include 

using namespace std;

int main() {
    int m, n;
    cin >> m >> n; // 输入网格的行数和列数

    // 读取一维输入并存储到 nums 数组中
    vector<int> nums(m * n);
    for (int i = 0; i < m * n; i++) {
        cin >> nums[i];
    }

    int tx, ty;
    cin >> tx >> ty; // 输入目标位置的行和列坐标

    // 将一维数组转为二维网格，同时记录所有信号源的位置
    vector<vector<int>> grid(m, vector<int>(n)); // 初始化二维网格
    vector<pair<int, int>> sources;             // 存储信号源的位置

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            grid[i][j] = nums[i * n + j]; // 从一维数组转换到二维网格
            if (grid[i][j] > 0) {        // 如果是信号源，记录其位置
                sources.push_back({i, j});
            }
        }
    }

    // 定义四个方向的移动向量（上下左右）
    vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    // 初始化 BFS 队列并将所有信号源加入队列
    queue<pair<int, int>> q;
    for (auto& source : sources) {
        q.push(source);
    }

    // 广度优先搜索 (BFS) 模拟信号传播
    while (!q.empty()) {
        auto [x, y] = q.front(); // 取出队首元素
        q.pop();

        // 遍历四个方向
        for (auto& [dx, dy] : directions) {
            int nx = x + dx, ny = y + dy; // 计算新位置的坐标

            // 检查新位置是否在网格范围内且未被信号覆盖
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                grid[nx][ny] = grid[x][y] - 1; // 更新新位置的信号强度
                if (grid[nx][ny] > 0) {       // 如果信号强度大于 0，将其加入队列
                    q.push({nx, ny});
                }
            }
        }
    }

    // 输出目标位置的信号强度
    cout << grid[tx][ty] << endl;

    return 0;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

C解法

解题思路
采用广度优先搜索（BFS）模拟信号的传播过程：
初始化信号源队列 sources，将所有信号源的位置加入队列。
遍历队列中的每个信号源，向其上下左右的方向传播信号：
若某位置信号值尚未覆盖（为 0），则更新该位置信号值为当前信号 - 1；
若更新后的信号值仍大于 0，将该位置加入队列以继续传播。
循环直至所有信号源的传播结束。


 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

JS解法

解题思路
问题描述

给定一个二维网格，包含以下类型的值：
0 表示无信号区域；
正整数表示信号源，其值越大，信号强度越高。
信号可以向上下左右传播，每传播一步信号值减 1，直至信号值为 0 时停止传播。
输入目标位置 (tx, ty)，输出该位置的信号强度。
算法设计

采用广度优先搜索（BFS）模拟信号的传播过程：
初始化信号源队列 sources，将所有信号源的位置加入队列。
遍历队列中的每个信号源，向其上下左右的方向传播信号：
若某位置信号值尚未覆盖（为 0），则更新该位置信号值为当前信号 - 1；
若更新后的信号值仍大于 0，将该位置加入队列以继续传播。
循环直至所有信号源的传播结束。
输入输出格式

输入：
第一行：网格的行数 m 和列数 n；
第二行：一维数组表示网格中的信号值；
第三行：目标位置 (tx, ty)。
输出：目标位置的信号强度。
流程

将一维数组转为二维网格；
将所有信号源记录为队列的初始状态；
使用 BFS 模拟信号传播过程；
输出目标位置的信号值

const readline = require('readline');

// 创建读写接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

// 存储输入数据
const input = [];

// 按行读取输入
rl.on('line', (line) => {
    input.push(line);

    // 当读取到三行输入时开始处理
    if (input.length === 3) {
        const [m, n] = input[0].split(' ').map(Number); // 读取网格的行数和列数
        const nums = input[1].split(' ').map(Number);  // 读取一维信号值数组
        const [tx, ty] = input[2].split(' ').map(Number); // 读取目标位置坐标

        const grid = [];  // 初始化二维网格
        let sources = []; // 初始化信号源队列

        // 将一维数组转为二维网格并记录信号源
        for (let i = 0; i < m; i++) {
            grid.push(nums.slice(i * n, (i + 1) * n)); // 从一维数组切片生成二维网格
            for (let j = 0; j < n; j++) {
                if (grid[i][j] > 0) sources.push([i, j]); // 如果是信号源，记录其位置
            }
        }

        // 定义四个方向的移动向量（上下左右）
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

        // BFS 模拟信号传播
        while (sources.length) {
            const [x, y] = sources.shift(); // 取出队列头部的信号源

            // 遍历信号传播的四个方向
            for (const [dx, dy] of directions) {
                const nx = x + dx, ny = y + dy; // 计算新位置坐标

                // 检查新位置是否在网格范围内且未被信号覆盖
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 0) {
                    grid[nx][ny] = grid[x][y] - 1; // 更新新位置的信号值
                    if (grid[nx][ny] > 0) sources.push([nx, ny]); // 若信号值仍大于 0，加入队列
                }
            }
        }

        // 输出目标位置的信号强度
        console.log(grid[tx][ty]);

        rl.close(); // 关闭读写接口
    }
});

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145058861"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

注册

评论记录：

未查询到任何数据！