华为OD机试 - 计算网络信号 - 2022Q4 A卷 - Py/Java/JS

题目：

        网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物

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，代表输入是一个mxn的数组。第二行是一串 m xn 如个用空格分隔的整数
每连续n个数代表一行，再往后 n个代表下一行，以此类推。对应的值代表对应的网格是空矿位置，还是信号源，还是阻隔物。第三行是i、j，代表需要计算 array[i][j]的网络信号值。

注意:此处i和j均从 0 开始，即第一行i 为 0

输出描述
输出对应位置的网络信号值，如果网络信号未覆盖到，也输出0。
一个网格如果可以途径不同的传播衰减路径传达，取较大的值作为其信号值。

示例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 -1 0 0 0 0 0
1 4

输出：

2

示例2：

输入：

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
2 1

输出：

0

备注

1.m不一定等于n，m<100 n<100,网络信号之和小于1000。
2.信号源只有1个，阻隔物可能有0个或多个。
3.输入的 m，n 与第二行的数组是合法的，无需处理数量对不上的异常情况。
4.要求输出信号值的位置，不会是阻隔物。

JAVA 代码

import java.util.*;
import java.util.stream.Collectors;class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int m = in.nextInt();int n = in.nextInt();int[] matrix = new int[m * n];for (int i = 0; i < m * n; i++) {matrix[i] = in.nextInt();}int target_i = in.nextInt();int target_j = in.nextInt();LinkedList<Integer[]> queue = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i * n + j] > 0) {queue.addLast(new Integer[] {i, j});break;}}}int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};while (queue.size() > 0) {Integer[] pos = queue.removeFirst();int i = pos[0];int j = pos[1];if (matrix[i * n + j] - 1 == 0) {break;}for (int[] direction : directions) {int new_x = i + direction[0];int new_y = j + direction[1];if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n && matrix[new_x * n + new_y] == 0) {matrix[new_x * n + new_y] = matrix[i * n + j] - 1;queue.addLast(new Integer[] {new_x, new_y});}}}System.out.println(matrix[target_i * n + target_j]);}}

Py代码

import functoolsdef comp(a, b):return b-aparams = [int(x) for x in input().split(" ")]
m = params[0]
n = params[1]
matrix = [int(x) for x in input().split(" ")]
target_params = [int(x) for x in input().split(" ")]
target_i = target_params[0]
target_j = target_params[1]
#print(matrix)queue = []
for i in range(m):for j in range(n):if (matrix[i * n + j] > 0) :queue.append([i,j])breakdirections = [[-1, 0], [1, 0], [0, -1], [0, 1]]while (len(queue) > 0) :pos = queue[0]queue.pop(0)i = pos[0]j = pos[1]if (matrix[i * n + j] - 1 == 0) :breakfor direction in directions:new_x = i + direction[0];new_y = j + direction[1];if (new_x >= 0 and new_x < m and new_y >= 0 and new_y < n and matrix[new_x * n + new_y] == 0) :matrix[new_x * n + new_y] = matrix[i * n + j] - 1queue.append([new_x, new_y])print(matrix[target_i * n + target_j])

JS代码

let directions = [[-1, 0],[1, 0],[0, -1],[0, 1]]function main(matrix, target_pos) {let queue = []let m = matrix.lengthlet n = matrix[0].lengthfor (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (matrix[i][j] > 0) {queue.push([i, j])break}}}while (queue.length>0) {let source = queue[0]queue = queue.slice(1)if (matrix[source[0]][source[1]] - 1 === 0) {break}for (let direction of directions) {let new_x = source[0] + direction[0]let new_y = source[1] + direction[1]if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n && matrix[new_x][new_y] === 0) {matrix[new_x][new_y] = matrix[source[0]][source[1]] - 1queue.push([new_x, new_y])}}}console.log(matrix[target_pos[0]][target_pos[1]])
}main([[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])