Python 中的 Lee 算法

在本教程中，我们将学习 Lee 算法，它用于解决迷宫路由问题。我们将使用 Python 编程语言来实现此算法。迷宫路由问题是最有趣且常被问到的编程问题之一。Lee 算法是基于广度优先搜索算法的解决迷宫问题的几种方法之一。现在，让我们来理解问题陈述。

问题陈述

在此问题中，给定一个二进制矩形矩阵形式的迷宫，我们需要找到给定源单元到目标单元的最短路径。迷宫表示为 MxN 矩阵，其中每个元素可以是 0 或 1。只有当值为 1 时，我们才能创建路径。在任何给定时间，我们可以在四个方向中的一个方向移动一步。有效步骤将是 -

向上移动：(x, y) --> (x - 1, y)
向左移动：(x, y) --> (x, y - 1)
向下移动：(x, y) --> (x + 1, y)
向右移动：(x, y) --> (x, y + 1)

让我们以更好的方式解释它，以便我们能够轻松理解。假设给定的矩阵如下 -

输入 -

输出

Length of the shortest path is 3

解决方案方法

要解决此类问题，我们将使用基于广度优先搜索 (BFS) 过程的 Lee 算法。我们将使用队列和矩阵来识别哪些单元已被访问，并重复此过程，直到找到从源单元到目标单元的最短路径。

BFS 是寻找最短路径的最佳技术之一，因为它不是一次考虑一条路径；相反，它考虑从源开始的所有路径，并同时在所有这些路径上前进一个单位。让我们来理解这个算法。

算法

1. 首先，我们创建一个空队列并将矩阵的坐标（源单元，到源本身的距离为 0）存储其中。将其标记为已访问。
2. 在源单元上调用 BFS 过程。
3. 初始化一个与输入矩阵大小相同的布尔数组，并将所有值设置为 false。
4. 运行一个循环直到队列为空。
5. 从队列中出队前端单元。如果到达目标单元，则返回。否则，对于当前单元的四个相邻单元中的每一个，如果单元值为 1 且未被访问，则将单元入队并将其标记为
6. 如果在处理完所有队列节点后仍未到达目标，则返回 False。

伪代码

让我们来理解 Lee 算法的伪代码。

初始化移动数组=>

解释 -

在上面的伪代码中，我们首先创建两个数组 rowNums 和 colNum，它们用于通过将这些数组的值添加到当前单元坐标来访问当前单元的所有四个相邻单元。

• LeeAlgo() 方法检查给定的源单元和目标单元是否有效，即它们的值是否为 1。如果源或目标无效或无法形成路径，则返回 -1。
• 如果源和目标合适，我们使用所有值设置为 False 的 visited 矩阵进行初始化。我们还初始化一个空队列 (q)，然后将源单元添加到该队列并将其标记为已访问。
• 之后，我们运行循环直到队列为空，并通过从队列中弹出每个节点来检查它，然后进行处理。当前单元的坐标存储在指针中，然后我们检查坐标是否等于我们的目标单元，并返回到该指针的距离。如果未到达目标，我们使用 rowNum 和 colNum 数组检查所有相邻单元，如果可以通过它们形成路径并且它们尚未被访问，则将它们添加到我们的队列中。这样，我们就应用了 BFS 模式，通过检查从当前单元开始的所有可能路径。
• 上面的循环一直迭代，直到到达目标或队列为空。如果队列在访问目标单元之前变空，则表示无法从源单元到达目标单元，在这种情况下，我们返回 -1。

现在将上述伪代码实现到 Python 代码中。

Python 代码

输出

Length of the Shortest Path is: 3

解释 -

在代码中，我们从“collections”模块导入“deque”和“namedtuple”类。

“ROW”和“COL”变量在开始时定义，用于设置迷宫的尺寸。“namedtuple”类用于创建两个自定义类“Cell”和“Node”，它们分别存储有关迷宫中单元的坐标以及到源的距离的信息。

“LeeAlgo”函数接收三个参数：代表迷宫的二维矩阵，“src”单元和“dest”单元。函数首先检查源单元和目标单元是否有效（即，它们在矩阵中是否设置为 1）。如果不是，则函数返回 -1。

然后，函数初始化一个名为“visited”的二维布尔数组，用于跟踪迷宫中哪些单元已被访问。源单元被标记为已访问。

创建一个“deque”，并将源单元添加到其中，距离为 0。然后，一个 while 循环迭代 deque，使用广度优先搜索 (BFS) 来探索迷宫。循环持续到 deque 为空。

对于每次迭代，函数会检查当前单元是否为目标单元。如果是，则返回到源的距离。否则，函数会查看所有相邻单元（上、下、左、右），如果单元有效（即，在矩阵中设置为 1 且尚未被访问），则将其添加到 deque 并标记为已访问。

最后，如果在源到目标的路径未找到，则函数返回 -1。

在代码的最后，创建了一个矩阵来表示迷宫，并定义了源和目标坐标。使用这些输入调用“LeeAlgo”函数，并打印出从源到目标的距离。

复杂度分析

在上述解决方案中，我们逐个遍历每个单元，直到到达目标单元。所有这些过程导致 0(MxN) 的时间复杂度，其中 M 和 N 是矩阵的维度。另外，由于我们需要一个额外的 MxN 矩阵来存储单元的访问状态，因此空间复杂度也为 O(MxN)。