保定建设工程信息网站,wordpress主题 简洁,seo网站结构优化,网页小游戏网址大全题目描述#xff1a; 网络信号经过传递会逐层衰减#xff0c;且遇到阻隔物无法直接穿透#xff0c;在此情况下需要计算某个位置的网络信号值。注意#xff1a;网络信号可以绕过阻隔物 array[m][n]的二维数组代表网格地图#xff0c; array[i][j]0代表i行j列是空旷位置 网络信号经过传递会逐层衰减且遇到阻隔物无法直接穿透在此情况下需要计算某个位置的网络信号值。注意网络信号可以绕过阻隔物 array[m][n]的二维数组代表网格地图 array[i][j]0代表i行j列是空旷位置array[i][j]x(x为正整数)代表i行j列是信号源信号强度是xarray[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列的网络信号值如下图值为2 输出描述 输出对应位置的网络信号值如果网络信号未覆盖到也输出0。 一个网格如果可以途经不同的传播衰减路径传达取较大的值作为其信号值。 补充说明 1、m不一定等于nm100n100网络信号值小于1000 2、信号源只有1个阻隔物可能有0个或多个 3、输入的mn与第二行的数组是合法的无需处理数量对不上的异常情况 4、要求输出信号值的位置不会是阻隔物示例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 2 1 输出 0 说明示例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 1 4 输出 2 说明 题目描述 网络信号经过传递会逐层衰减且遇到阻隔物无法直接穿透在此情况下需要计算某个位置的网络信号值。注意网络信号可以绕过阻隔物 array[m][n]的二维数组代表网格地图 array[i][j]0代表i行j列是空旷位置array[i][j]x(x为正整数)代表i行j列是信号源信号强度是xarray[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列的网络信号值如下图值为2 输出描述 输出对应位置的网络信号值如果网络信号未覆盖到也输出0。 一个网格如果可以途经不同的传播衰减路径传达取较大的值作为其信号值。 补充说明 1、m不一定等于nm100n100网络信号值小于1000 2、信号源只有1个阻隔物可能有0个或多个 3、输入的mn与第二行的数组是合法的无需处理数量对不上的异常情况 4、要求输出信号值的位置不会是阻隔物示例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 2 1 输出 0 说明示例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 1 4 输出 2 说明 题解
BFS 广度优先算法寻找最短路径
信号值 - 步数
源码
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {// 方向数组用于表示上下左右四个方向static int[][] directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 读取输入的网格大小 m 和 nint m scanner.nextInt();int n scanner.nextInt();// 初始化网格int[][] array new int[m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {array[i][j] scanner.nextInt();}}// 读取目标位置int targetI scanner.nextInt();int targetJ scanner.nextInt();// 初始化信号强度数组-1表示未访问int[][] signal new int[m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {signal[i][j] -1;}}// BFS队列队列中存储 (x, y, signal_strength)Queueint[] queue new LinkedList();// 寻找信号源将信号源的位置加入队列for (int i 0; i m; i) {for (int j 0; j n; j) {if (array[i][j] 0) { // 找到信号源queue.offer(new int[]{i, j, array[i][j]});signal[i][j] array[i][j]; // 初始信号值为信号源的值}}}// 开始BFSwhile (!queue.isEmpty()) {int[] current queue.poll();int x current[0];int y current[1];int currentSignal current[2];// 遍历四个方向for (int[] dir : directions) {int newX x dir[0];int newY y dir[1];// 判断是否越界或遇到阻隔物if (newX 0 newX m newY 0 newY n array[newX][newY] ! -1) {int newSignal currentSignal - 1;// 只有信号强度大于0并且比当前信号值大时才更新if (newSignal 0 newSignal signal[newX][newY]) {signal[newX][newY] newSignal;queue.offer(new int[]{newX, newY, newSignal});}}}}// 输出指定位置的信号值如果未覆盖到输出0System.out.println(signal[targetI][targetJ] ! -1 ? signal[targetI][targetJ] : 0);}
}
