题目描述
网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值 注意:网络信号可以绕过阻隔物
array[m][n] 的二维数组代表网格地图
array[i][j] = 0 代表第是空旷位置
array[i][j] = x (x为正整数)代表 是信号源，信号强度是
array[i][j] = -1代表 是阻隔物
信号源只有
1个，阻隔物可能有0个或多个
网络信号衰减是上下左右相邻的网格衰减1
现要求输出 对应位置的网络信号值
输入描述
输入为三行
- 第一行为
代表输入是一个
的数组
- 第二行是一串 个用空格分隔的整数
- 每连续 n 个数代表一行，
- 再往后 n 个代表下一行，以此类推。
- 对应的值代表对应的网格是空旷位置，还是信号源，或是阻隔物
- 第三行是 代表需要计算
array[i][j]的网络信号值
- 注意:此处
均从 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
1 4代表如下地图
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 列的网格信号值 信号源处信号强度为 4 ，信号经过衰减在 第 1 行、第 4 列的网格信号值是 2
输出描述
输出对应位置的网格信号值，如果网格信号未达到，输出 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 0 0 0 0 0 0
2 1
--输出
0
--说明
无show code
package com.hw;
import java.util.Scanner;
/**
* desc : <a href="https://fcqian.blog.csdn.net/article/details/128233067">计算网络信号、信号强度</a>
* <p>
* create time : 2023/8/12 15:54
*/
public class CalculateSignal {
private static int i;
private static int j;
private static int[][] chart;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int m = in.nextInt();
int n = in.nextInt();
chart = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
chart[i][j] = in.nextInt();
}
}
i = in.nextInt();
j = in.nextInt();
calculateSignal(m, n);
}
}
/*
* 信号源的位置首先是不确定的，那么首先可以先找到信号源的位置。
* 假设信号源的位置确定之后是 (x, y)
* --然后需要确定 从点 (x, y) 到目标点 (i, j) 的所有可达路径.
* --然后找到最大的信号强度.
*
* --那么从信号源出发的话，每一次有上下左右四个方向的选择.
* ----遇到障碍的话，路径打断，去过的位置进行标记，避免重复.
* ----信号源每次传播一次，信号强度衰减 1，当信号强度为 0 的时候中断.
* ----当遇到 目标点的时候，记录当前传播路径的的信号强度，最后输出最大的信号强度.
*/
private static int x;
private static int y;
private static int ans;
private static void calculateSignal(int m, int n) {
// 先找到信号源头的位置.
for (int k = 0; k < m; k++) {
for (int l = 0; l < n; l++) {
if(chart[k][l] != 0 && chart[k][l] != -1) {
// 找到了信号源头的位置.
x = k;
y = l;
}
}
}
// 信号源位置是 (x, y)
if(x == i && y == j) {
// 信号源位置 和 需要计算的网格信号值的位置一样
System.out.println(chart[x][y]);
return;
}
// 设计签名函数
// --现在我要干什么？——需要从 (x, y) 出发到点 (i, j)
// --记录一下当前的信号强度
// --用一个数组记录到达过的位置
// --从那一个位置出发，以及当前所到达的位置
boolean[][] arrived = new boolean[m][n];
// 初始化，在 (x, y) 位置，这个时候，标记为 true.
arrived[x][y] = true;
ans = 0;
dfs(chart[x][y], arrived, x, y);
System.out.println(ans);
}
// 上下左右 四个方向.
// 右：列+1
// 左：列-1
// 上：行-1
// 下：行+1
private static final int[][] directions = {{0, 1}, {-1, 0}, {-1, 0}, {1, 0}};
private static void dfs(int signal, boolean[][] arrived, int x, int y) {
// 首先-终止条件.
if(x == i && y == j && signal >= 0) {
// 到达了目标位置，可以之间返回当前信号强度了.
ans = Math.max(ans, signal);
return;
}
// 信号强度 等于0，直接返回.
// 等于 0 之后还没有到达目标点的话，就直接返回了.
if(signal == 0) {
return;
}
// 从点 x,y 出发，走 上下左右 四个方向走.
for (int[] direction : directions) {
int newX = x + direction[0];
int newY = y + direction[1];
// 首先判断是否越界
if(newX < 0 || newX >= arrived.length || newY < 0 || newY >= arrived[0].length) {
continue;
}
// 如果这个点到达过了 或者 遇到障碍--跳过 并且还不能越界
if(arrived[newX][newY] && chart[newX][newY] == -1) {
continue;
}
arrived[newX][newY] = true;
dfs(signal - 1, arrived, newX, newY);
arrived[newX][newY] = false;
}
}
}