AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

P3700. 计算网络信号

中等通过率 55% · 提交 546 · 通过 301
BFS队列模拟图论

小慕正在处理一个网络信号传播问题。信号在网格中传播时会逐层,且遇到无法直接穿透,但可以绕过阻隔物继续传播。现在需要计算某个位置的网络信号值。 - 给定一个 m 行 n 列的二维网格地图, - 网格中 array[i][j] = 0 表示该位置为空旷区域; - array[i][j] = x(x 为正整数)表示该位置是信号源,信号强度为 x; - array[i][j] = -1 表示该位置是阻隔物。 - 整个地图中只有 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 代表如下地图 ![image.png](/api/public/img/4545658b97c24f9bb20f4149c2d778bb.png) 需要输出第 1 行第 4 列的网络信号值,如下图,值为 2 ![image.png](/api/public/img/c3fa450b286945739479fba1cce805b7.png)

输出描述

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

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
i=0 i=1 i=2 i=3 j=0 j=1 j=2 j=3 j=4 0 0 0 -1 0 0 0 0 0 2 0 0 -1 4 0 0 0 0 0 0 信号源 阻隔物 目标位置 衰减1 衰减1
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「计算网络信号」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。