Java Program to Find Distance of Nearest Cell Having 1 in a Binary Matrix

问题陈述

给定一个二元矩阵（其中每个单元格只包含 0 或 1），任务是确定从 0 单元格到 1 单元格所需的最少移动次数。如果当前单元格已经是 1，则距离为 0。

我们的问题是为每个新的 0 单元格标记最近的 1 单元格的距离。给定问题可以通过一系列称为广度优先搜索 (BFS) 的算法轻松解决，因为 BFS 可以轻松解决非加权图中的最短路径问题。

问题解决方案

我们得到了一个只包含二元值的矩阵，对于每个包含“0”的单元格，都需要找到与包含“1”的单元格的最短距离。此外，所呈现的信息可以很容易地可视化为图的形式，其中每个单元格对应一个节点，如果两个单元格是邻居，则它们之间存在连接。

目的是确定节点（值为 0 的单元格）到第一个值为 1 的节点（单元格）的整体距离。解决此问题的唯一方法是通过 BFS，它是最合适的方法。

BFS 在节点级别工作，并且可以证明在 BFS 中，我们第一次从包含 0 的单元格遍历到包含 1 的单元格时，我们就找到了最短路径的长度。

解决问题的步骤

• 初始化结果矩阵：这将存储相应单元格的最小距离。
• 使用队列进行 BFS 遍历：BFS 可以同时在所有包含 1 的单元格上启动。这可以通过将所有包含 1 的单元格放入初始队列，同时处理相邻单元格来完成。
• 四向移动：如果每个单元格有 4 个邻居，即当前单元格的上方、下方、左方和右方，则在 BFS 期间必须探索所有这些邻居。
• 标记已访问节点：这是为了避免重复访问节点，同时我们还应确保不覆盖找到的最小距离。

让我们在 Java 程序中实现上述步骤。

文件名：NearestCellWithOne.java

输出

 
Input Binary Matrix:
0 0 0 1 
0 1 0 0 
1 0 0 0 
0 0 1 0 
Distance Matrix:
2 1 1 0 
1 0 1 1 
0 1 1 2 
1 1 0 1   

时间复杂度和空间复杂度

每个单元格仅处理一次，并且每个相邻单元格仅考虑一次。因此，时间复杂度为O(R × C)，其中 R 是矩阵的行数，C 是列数。

所需的空间为O(R × C)，用于存储结果矩阵和队列。

结论

它利用 BFS 结果，通过分层节点遍历有效地解决问题。这确保了我们从每个包含 0 的单元格到最近的 1 的最小距离。

O(R × C) 的时间复杂度意味着即使对于大型矩阵，该解决方案也只需要很短的时间。这种方法对于非加权网格（如本问题中使用的网格）中的最短路径问题非常有效。