逃离大型迷宫 Python

pythonserver side programmingprogramming更新于 2026/1/22 5:32:17

假设我们有一个网格，有 100 万行和 100 万列，我们还有一个阻塞单元格列表。现在我们将从源方块开始并想要到达目标方块。每次移动时，我们都可以走到网格中上、下、左、右相邻的方格，这些方格不在给定的阻塞单元格列表中。

我们必须检查是否可以通过一系列移动到达目标方格。

因此，如果输入为blocked = [[0,1],[1,0]], source = [0,0], target = [0,3]，则输出为False

为了解决这个问题，我们将遵循以下步骤 −

blocked := 创建所有阻塞单元格的集合
定义一个方法 dfs()，它将采用 x、y、target 和 seen
如果 (x,y) 不在网格范围内或 (x,y) 在blocked 中或 (x,y) 在seen 中，则
- 返回 false
将 (x,y) 添加到 seen
如果 seen 的大小 > 20000 或 (x,y) 为目标，则
- 返回 true
返回 dfs(x+1,y,target,seen) 或 dfs(x-1,y,target,seen) 或 dfs(x,y+1,target,seen) 或 dfs(x,y-1,target,seen)
返回 dfs(source[0], source[1], target, empty set) 和 dfs(target[0], target[1], source, empty set)

让我们看看下面的实现以便更好地理解 −

示例

class Solution(object):
   def isEscapePossible(self, blocked, source, target):
      blocked = set(map(tuple, blocked))
      def dfs(x, y, target, seen):
         if not (0 <= x < 10**6 and 0 <= y < 10**6) or (x, y) in blocked or (x, y) in seen: return             False
         seen.add((x, y))
         if len(seen) > 20000 or [x, y] == target: return True
         return dfs(x + 1, y, target, seen) or \
            dfs(x - 1, y, target, seen) or \
            dfs(x, y + 1, target, seen) or \
            dfs(x, y - 1, target, seen)
         return dfs(source[0], source[1], target, set()) and
dfs(target[0], target[1], source, set())
ob = Solution()
print(ob.isEscapePossible([[0,1],[1,0]], [0,0], [0,3]))