60、計(jì)算網(wǎng)絡(luò)信號(hào)

題目

網(wǎng)絡(luò)信號(hào)經(jīng)過(guò)傳遞會(huì)逐層衰減，且遇到阻隔物無(wú)法直接穿透，在此情況下需要計(jì)算某個(gè)位置的網(wǎng)絡(luò)信號(hào)值。注意:網(wǎng)絡(luò)信號(hào)可以繞過(guò)阻隔物
array[m][n]，二維數(shù)組代表網(wǎng)格地圖
array[i][j]=0，代表i行j列是空曠位置
array[i][j]= x，(x為正整數(shù))代表i行j列是信號(hào)源，信號(hào)強(qiáng)度是x,
array[i][j]=-1， 代表i行j列是阻隔物
信號(hào)源只有1個(gè)，阻隔物可能有0個(gè)或多個(gè)；
網(wǎng)絡(luò)信號(hào)袁減是上下左右相鄰的網(wǎng)格衰減1現(xiàn)要求輸出對(duì)應(yīng)位置的網(wǎng)絡(luò)信號(hào)值。

輸入
輸入為三行，
第一行為 m、n，代表輸入是一個(gè)mxn 的數(shù)組,
第二行是一串 mxn 如個(gè)用空格分隔的整數(shù)每連續(xù)n個(gè)數(shù)代表一行，再往后n個(gè)代表下一行，以此類(lèi)推。對(duì)應(yīng)的值代表對(duì)應(yīng)的網(wǎng)格是空礦位置，還是信號(hào)源，還是阻隔物，
第三行是ì、j，代表需要計(jì)算 array[i][j] 的網(wǎng)絡(luò)信號(hào)值。注意:此處i和j均從 0開(kāi)始，即第一行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

輸出
輸出對(duì)應(yīng)位置的網(wǎng)絡(luò)信號(hào)值，如果網(wǎng)絡(luò)信號(hào)未覆蓋到，也輸出0。
一個(gè)網(wǎng)格如果可以途徑不同的傳播衰減路徑傳達(dá)，取較大的值作為其信號(hào)值。

解題思路

把信號(hào)源向上下左右四個(gè)方向擴(kuò)散，并把滿足條件的擴(kuò)散點(diǎn)作為新的信號(hào)源繼續(xù)擴(kuò)散，直到信號(hào)值為0、或者擴(kuò)散到“坐標(biāo)系”邊緣

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

對(duì)于以上輸入，得到的二維數(shù)組(可視為坐標(biāo)系)為

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

擴(kuò)散后，最終為

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

這里一定要注意，二維數(shù)組和我們上學(xué)時(shí)常用的xy軸坐標(biāo)系還是有區(qū)別的，它們的原點(diǎn)不同，下面簡(jiǎn)化一下以上二維數(shù)組坐標(biāo)系示意圖

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

這個(gè)輸入，要求的輸出array[1][4]，它的結(jié)果是2；
我一開(kāi)始把二維數(shù)組和上學(xué)時(shí)的xy軸坐標(biāo)系給搞混了，死活想不明白(1，4)為啥是2，而不是1？

java代碼

沒(méi)有作輸入的合法性校驗(yàn)，有興趣的可以自己補(bǔ)充一下；
變量名起的也比較隨意，大家不要學(xué)我

import java.util.LinkedList;
import java.util.Scanner;public class A60計(jì)算網(wǎng)絡(luò)信號(hào) {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;}}
}