P3700. 计算网络信号

解题思路

注意，本题和 腐烂的橘子 几乎完全一致，属于计算 BFS 层数 的问题，而且只有一个信号源，所以使用常规的 单源 BFS 方法即可完成。

要点说明

• 输入的数据是一个长度为 m * n 的一维数组，需要转换成我们常用的 grid 二维矩阵。
• 本题可以直接在 grid 上进行元素修改，最终输出要求的点 (target_x, target_y) 的强度值 grid[target_x][target_y] 即可。
• 由于直接对 grid 进行修改，如果某个点的强度已经从 0 修改为其他值，说明已经进入过，故无需重复使用 checkList 进行检查。
• 搜索层数可以从信号源的强度 intensity 不断 -1 来判断，无需从 level = 0 开始递增。

思路展开

• 输入给的是长度为 m*n 的一维数组，代码先按每 n 个元素切成一行还原出二维 grid，后续才能用行列坐标做四方向搜索。
• 双重循环找到唯一的信号源（值大于 0 的格子），把它入队作为 BFS 起点，并记下初始强度 intensity。
• BFS 按层推进：while 每进入一轮先令 intensity 减 1，表示信号又向外扩散了一格；若 intensity 减到 0 就直接停止，因为再往外强度已经耗尽。每轮先取当前队列长度 qSize，保证本轮只处理同一层的格子，这是分层 BFS 的标准写法。
• 对出队格子的上下左右邻居，只要不越界且值为 0（空旷区域），就把该格直接改写成当前的 intensity 并入队。值为 -1 的阻隔物和已经写过强度的格子都不满足等于 0 的条件，自然被跳过——对 grid 的就地修改同时起到了 checkList 防重复访问的作用，也正好体现了信号不穿透阻隔物、但可以绕行传播的规则。
• 传播结束后直接输出目标位置 (target_x, target_y) 上的值：可能是被写入的信号强度，也可能仍保持初始值 0，表示信号未能到达该点。

复杂度分析 设网格为 m 行 n 列。

• 还原二维数组与寻找信号源都是对全网格的一次扫描，各为 O(m*n)。
• BFS 阶段：每个格子只有在值为 0 时才会被改写并入队，改写后不再满足入队条件，因此每个格子至多入队、出队一次，每次出队检查 4 个邻居是常数量工作，搜索整体为 O(m*n)；若强度提前衰减到 0，实际访问的格子只会更少。

总时间复杂度 O(m*n)，瓶颈是对网格的整体扫描加一次 BFS。空间复杂度 O(m*n)：grid 本身占 O(m*n)，队列最坏时容纳一整层格子，也不超过 O(m*n)。