华为OD机试 - 信号强度（Python/JS/C/C++ 2024 E卷 100分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。
注意：
- 网络信号可以绕过阻隔物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
代表如下地图
需要输出第2行第1列的网络信号值。
三、输出描述
输出对应位置的网络信号值，如果网络信号未覆盖到，也输出0。
一个网格如果可以途经不同的传播衰减路径传达，取较大的值作为其信号值。
四、补充说明
- m不一定等于n，m<100，n<100，网络信号值小于1000；
- 信号源只有1个，阻隔物可能有0个或多个；
- 输入的m，n与第二行的数组是合法的，无需处理数量对不上的异常情况；
- 要求输出信号值的位置，不会是阻隔物
五、解题思路
- 读取输入的m和n，表示数组的行数和列数。
- 创建一个大小为m*n的二维数组arr来存储输入的网格地图。
- 使用变量x和y记录信号源的坐标，初始化为0。
- 使用两重循环遍历输入的m*n个整数，同时找到信号源的坐标。
- 读取结果坐标x1和y1。
- 调用递归函数get(x, y, arr)来计算网络信号值。
- 输出arr[x1][y1]作为结果。
递归函数get(x, y, arr)的思路如下：
- 获取arr的行数m和列数n。
- 如果x或y超出数组的边界，直接返回。
- 如果arr[x][y]小于等于1，说明该位置已经被覆盖，直接返回。
- 创建一个数组arr2，其中每个元素表示相邻位置的偏移量，分别为左、右、上、下。
- 遍历arr2中的每个偏移量：
- 计算相邻位置的坐标a和b。
- 如果a或b超出数组的边界，跳过当前循环。
- 如果arr[a][b]为-1，说明该位置是阻隔物，跳过当前循环。
- 如果arr[x][y]-1大于arr[a][b]，说明通过当前位置可以提供更强的信号，更新arr[a][b]的值为arr[x][y]-1。
- 调用递归函数get(a, b, arr)继续向相邻位置传播信号。
- 递归函数结束。
六、Python算法源码
def get(x, y, arr):
m = len(arr)
n = len(arr[0])
# 边界检查
if x < 0 or x >= m or y < 0 or y >= n:
return
if arr[x][y] <= 1:
return
# 方向数组，用于上下左右移动
directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
for direction in directions:
a = x + direction[0]
b = y + direction[1]
# 检查是否在数组边界内
if 0 <= a < m and 0 <= b < n:
# 跳过值为-1的位置
if arr[a][b] == -1:
continue
# 如果当前位置信号更强，更新并递归
if arr[x][y] - 1 > arr[a][b]:
arr[a][b] = arr[x][y] - 1
# 递归
get(a, b, arr)
def main():
m = int(input("请输入行数: "))
n = int(input("请输入列数: "))
arr = []
# 初始化数组并获取信号源位置
x, y = 0, 0
for i in range(m):
row = list(map(int, input().split()))
arr.append(row)
for j in range(n):
if arr[i][j] > 0:
x, y = i, j
# 获取结果坐标
x1 = int(input("请输入结果的横坐标: "))
y1 = int(input("请输入结果的纵坐标: "))
# 处理信号扩散
get(x, y, arr)
# 输出结果
print(arr[x1][y1])
if __name__ == "__main__":
main()
七、JavaScript算法源码
function get(x, y, arr) {
const m = arr.length;
const n = arr[0].length;
// 边界检查
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
}
if (arr[x][y] <= 1) {
return;
}
// 方向数组，用于上下左右移动
const directions = [
[0, -1], [0, 1], [-1, 0], [1, 0]
];
for (const direction of directions) {
const a = x + direction[0];
const b = y + direction[1];
// 检查是否在数组边界内
if (a >= 0 && a < m && b >= 0 && b < n) {
// 跳过值为-1的位置
if (arr[a][b] === -1) {
continue;
}
// 如果当前位置信号更强，更新并递归
if (arr[x][y] - 1 > arr[a][b]) {
arr[a][b] = arr[x][y] - 1;
// 递归
get(a, b, arr);
}
}
}
}
function main() {
const m = parseInt(prompt("请输入行数: "), 10);
const n = parseInt(prompt("请输入列数: "), 10);
const arr = [];
// 初始化数组并获取信号源位置
let x = 0, y = 0;
for (let i = 0; i < m; i++) {
const row = prompt(`请输入第${i + 1}行的元素（以空格分隔）: `).split(' ').map(Number);
arr.push(row);
for (let j = 0; j < n; j++) {
if (arr[i][j] > 0) {
x = i;
y = j;
}
}
}
// 获取结果坐标
const x1 = parseInt(prompt("请输入结果的横坐标: "), 10);
const y1 = parseInt(prompt("请输入结果的纵坐标: "), 10);
// 处理信号扩散
get(x, y, arr);
// 输出结果
console.log(arr[x1][y1]);
}
main();
八、C算法源码
#include <stdio.h>
#include <stdlib.h>
// 递归函数用于扩散信号
void get(int x, int y, int **arr, int m, int n) {
// 边界检查
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
}
if (arr[x][y] <= 1) {
return;
}
// 方向数组，用于上下左右移动
int directions[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
for (int i = 0; i < 4; i++) {
int a = x + directions[i][0];
int b = y + directions[i][1];
// 检查是否在数组边界内
if (a >= 0 && a < m && b >= 0 && b < n) {
// 跳过值为-1的位置
if (arr[a][b] == -1) {
continue;
}
// 如果当前位置信号更强，更新并递归
if (arr[x][y] - 1 > arr[a][b]) {
arr[a][b] = arr[x][y] - 1;
// 递归
get(a, b, arr, m, n);
}
}
}
}
int main() {
int m, n;
// 输入行数和列数
printf("请输入行数: ");
scanf("%d", &m);
printf("请输入列数: ");
scanf("%d", &n);
// 动态分配二维数组
int **arr = (int **)malloc(m * sizeof(int *));
for (int i = 0; i < m; i++) {
arr[i] = (int *)malloc(n * sizeof(int));
}
// 初始化数组并获取信号源位置
int x = 0, y = 0;
printf("请输入数组元素（每行 %d 个，以空格分隔）：\n", n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &arr[i][j]);
if (arr[i][j] > 0) {
x = i;
y = j;
}
}
}
// 输入结果的坐标
int x1, y1;
printf("请输入结果的横坐标: ");
scanf("%d", &x1);
printf("请输入结果的纵坐标: ");
scanf("%d", &y1);
// 处理信号扩散
get(x, y, arr, m, n);
// 输出结果
printf("结果：%d\n", arr[x1][y1]);
// 释放内存
for (int i = 0; i < m; i++) {
free(arr[i]);
}
free(arr);
return 0;
}
九、C++算法源码
#include <iostream>
#include <vector>
using namespace std;
// 递归函数用于扩散信号
void get(int x, int y, vector<vector<int>>& arr) {
int m = arr.size();
int n = arr[0].size();
// 边界检查
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
}
if (arr[x][y] <= 1) {
return;
}
// 方向数组，用于上下左右移动
int directions[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
for (int i = 0; i < 4; i++) {
int a = x + directions[i][0];
int b = y + directions[i][1];
// 检查是否在数组边界内
if (a >= 0 && a < m && b >= 0 && b < n) {
// 跳过值为-1的位置
if (arr[a][b] == -1) {
continue;
}
// 如果当前位置信号更强，更新并递归
if (arr[x][y] - 1 > arr[a][b]) {
arr[a][b] = arr[x][y] - 1;
// 递归
get(a, b, arr);
}
}
}
}
int main() {
int m, n;
// 输入行数和列数
cout << "请输入行数: ";
cin >> m;
cout << "请输入列数: ";
cin >> n;
// 初始化二维数组
vector<vector<int>> arr(m, vector<int>(n));
// 初始化数组并获取信号源位置
int x = 0, y = 0;
cout << "请输入数组元素（每行 " << n << " 个，以空格分隔）：\n";
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if (arr[i][j] > 0) {
x = i;
y = j;
}
}
}
// 输入结果的坐标
int x1, y1;
cout << "请输入结果的横坐标: ";
cin >> x1;
cout << "请输入结果的纵坐标: ";
cin >> y1;
// 处理信号扩散
get(x, y, arr);
// 输出结果
cout << "结果: " << arr[x1][y1] << endl;
return 0;
}
🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
