在一个二维网格地图中,信号从唯一的信号源出发,经过空旷位置向四个方向传播,但遇到阻隔物无法穿透。给定地图的行数和列数、各个网格的状态(空旷位置、信号源和阻隔物),以及要计算的特定位置,要求输出该位置的网络信号值。如果没有信号覆盖该位置,则输出 0。例如,输入描述了一个 6 行 5 列的地图,计算位置 (1, 4) 的网络信号值,结果为 2。
输入读取:首先,我们需要读取网格的尺寸 (m \times n) 和网格数据,接着获取需要计算的目标位置。
信号源定位:在网格中找到信号源的位置及其初始信号强度。信号源是唯一的,因此只需遍历一次网格。
网络信号经过传递会逐层衰减,且遇到阻隔物无法直接穿透,在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物。
现要求输出对应位置的网络信号值。
输入为三行,
注意:此处 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
代表如下地图
需要输出第1行第4列的网络信号值,如下图,值为2。
输出对应位置的网络信号值,如果网络信号未覆盖到,也输出 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
输入
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