优化实现：二维数组中指定位置最近负数的高效查找方法

核心方案：多源广度优先搜索（BFS） #

针对批量计算所有非0元素到目标类型的最近车步距（曼哈顿距离，横纵向步数之和），多源BFS是效率最优的选择，完全满足43×24数组的时间要求（单次运行远低于0.5秒）。

步骤拆解 #

1. 初始化准备

   • 创建两个和原数组同维度的距离数组：neg_distance（存储正数到最近负数的距离）、pos_distance（存储负数到最近正数的距离），初始值全部设为-1（标记未计算）。
   • 准备两个队列：neg_queue（存放初始负数位置）、pos_queue（存放初始正数位置）。
   • 遍历原数组：
     • 遇到值为-1的位置：将其加入neg_queue，同时把neg_distance对应位置设为0（负数自身距离为0，后续忽略即可）。
     • 遇到值为1的位置：将其加入pos_queue，同时把pos_distance对应位置设为0。

2. 计算正数到最近负数的距离（第一次BFS）

   • 定义方向数组：directions = [(-1,0), (1,0), (0,-1), (0,1)]（对应上下左右四个车的移动方向）。
   • 循环处理neg_queue：
     • 取出队首位置(x, y)。
     • 遍历四个方向，得到相邻位置(nx, ny)。
     • 检查边界：nx需在0到行数-1之间，ny需在0到列数-1之间。
     • 若原数组(nx, ny)的值为1（正数，未计算距离），且neg_distance[nx][ny] == -1：
       • 设置neg_distance[nx][ny] = neg_distance[x][y] + 1（车步距每走一步加1）。
       • 将(nx, ny)加入neg_queue。

3. 计算负数到最近正数的距离（第二次BFS）

   • 复用方向数组，循环处理pos_queue：
     • 取出队首位置(x, y)。
     • 遍历四个方向得到(nx, ny)，检查边界。
     • 若原数组(nx, ny)的值为-1（负数，未计算距离），且pos_distance[nx][ny] == -1：
       • 设置pos_distance[nx][ny] = pos_distance[x][y] + 1。
       • 将(nx, ny)加入pos_queue。

4. 输出结果

   • 遍历原数组每个位置：
     • 若值为1：取neg_distance对应值作为最近负数的车步距。
     • 若值为-1：取pos_distance对应值作为最近正数的车步距。
     • 若值为0：无需处理。

效率说明 #

多源BFS的时间复杂度为O(M×N)（M为行数，N为列数），43×24数组仅需处理约2000次操作，完全符合≤0.5秒的要求，且扩展性强，数组更大时依然高效。相比逐个点做单点BFS（O((M×N)²)），性能提升显著。

新手注意事项 #

• 队列操作：推荐用语言自带的高效队列结构（如Python的collections.deque），避免用列表pop(0)导致的性能损耗。
• 边界检查：必须确保相邻位置在数组范围内，否则会出现越界错误。
• 初始值设置：用-1标记未计算位置，能清晰区分已处理和未处理的元素，避免重复计算。

内容的提问来源于stack exchange，提问作者Majestic_Monkey_