如何在二进制迷宫中找到最短路径

在这个问题中，我们给出了一个 m x n 的二元矩阵。矩阵只包含 1 和 0。矩阵中的 1 代表路径，0 代表死路。我们将给出两个单元格的地址。我们的任务是找到从源单元格到目标单元格的最短距离。让我们来看一个例子来理解这个问题。

输入

输出

The shortest path is 14

方法 - 1

在这个方法中，我们将执行 DFS，并通过回溯找到源单元格和目标单元格之间的最短路径。

以下是我们遵循的步骤

• 我们将从给定的源单元格地址开始，并继续向四个方向探索路径。
• 我们将继续探索，直到到达目标。通过这种方式，我们将检查这四个方向，从中我们可以到达目标单元格。
• 然后，通过回溯，我们将计算路径长度。我们将跟踪已访问的路径以避免循环。
• 最后，我们将返回可能的最短路径长度。

代码

输出

The shortest path length is 14

时间复杂度：此方法的 时间复杂度为 O(4 ^ M*N)，其中 M 和 N 是矩阵的维度。

空间复杂度：我们使用了一个矩阵来存储访问过的数组；因此，此方法的空间复杂度为 O(M * N)。

方法 - 2

在此方法中，我们将使用广度优先搜索算法来解决问题。对于 BFS，我们将使用队列数据结构。队列将为每个节点存储两样东西。第一样是单元格的坐标，第二样是该单元格到源单元格的距离。使用 BFS 算法的主要思想是，与 DFS 算法不同，BFS 算法一次处理所有路径。因此，它将在每个路径上前进一个单元格。通过该路径第一次到达目标单元格的路径将是最短路径。由于我们在队列中存储了单元格到源单元格的距离，因此我们也能获得路径长度。

这是此方法的算法。

• 这一次，我们将从源单元格开始。
• 我们将当前的单元格添加到节点中，以及它到源单元格的距离。
• 我们还将创建一个数组来跟踪已访问的节点。
• 然后，我们将循环队列直到它为空。
• 在循环中，我们将取出队列的第一个元素，并检查它是否与目标单元格相同。
• 如果未到达目标单元格，那么我们将向所有可能的方向前进。

代码

输出

The shortest path length is 14