华为OD算法题汇总

60、计算网络信号

题目

网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物
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 的数组,
第二行是一串 mxn 如个用空格分隔的整数每连续n个数代表一行，再往后n个代表下一行，以此类推。对应的值代表对应的网格是空矿位置，还是信号源，还是阻隔物，
第三行是ì、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

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

解题思路

把信号源向上下左右四个方向扩散，并把满足条件的扩散点作为新的信号源继续扩散，直到信号值为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

对于以上输入，得到的二维数组(可视为坐标系)为

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

扩散后，最终为

0 0  1 -1  1 
0 1  2  3  2 
0 0 -1  4  3 
0 1  2  3  2 
0 0  1  2 -1 
0 0  0  1  0

这里一定要注意，二维数组和我们上学时常用的xy轴坐标系还是有区别的，它们的原点不同，下面简化一下以上二维数组坐标系示意图

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

这个输入，要求的输出array[1][4]，它的结果是2；
我一开始把二维数组和上学时的xy轴坐标系给搞混了，死活想不明白(1，4)为啥是2，而不是1？

java代码

没有作输入的合法性校验，有兴趣的可以自己补充一下；
变量名起的也比较随意，大家不要学我

import java.util.LinkedList;
import java.util.Scanner;public class A60计算网络信号 {private static LinkedList<Danyuange> list = new LinkedList<>();private static int[][] zhouweiArr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] inputArr = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int d = sc.nextInt();inputArr[i][j] = d;if(d > 0) {Danyuange yuan = new Danyuange();yuan.setX(i);yuan.setY(j);yuan.setD(d);list.add(yuan);}}}int queryX = sc.nextInt();int queryY = sc.nextInt();while (list.size() > 0) {Danyuange danyuange = list.removeFirst();kuosanMethod(inputArr, danyuange);}System.out.println(inputArr[queryX][queryY]);}private static void kuosanMethod(int[][] inputArr, Danyuange danyuange) {int x = danyuange.getX();int y = danyuange.getY();int d = danyuange.getD();for (int i = 0; i < 4; i++) {int newX = x + zhouweiArr[i][0];int newY = y + zhouweiArr[i][1];if(newX >= 0 && newX < inputArr.length && newY >= 0 && newY < inputArr[0].length) {if(inputArr[newX][newY] == 0) {inputArr[newX][newY] = d - 1;}if(inputArr[newX][newY] < d && inputArr[newX][newY] >= 2 && inputArr[newX][newY] != -1) {Danyuange newDanyuange = new Danyuange();newDanyuange.setX(newX);newDanyuange.setY(newY);newDanyuange.setD(d-1);list.add(newDanyuange);}}}}private static class Danyuange {int x;int y;int d;public int getX() {return x;}public void setX(int x) {this.x = x;}public int getY() {return y;}public void setY(int y) {this.y = y;}public int getD() {return d;}public void setD(int d) {this.d = d;}}
}