逃离大型迷宫巨蟒

假设我们有一个网格，有一百万行和一百万列，我们还有一个被阻止的单元格列表。现在我们将从源正方形开始，并想要到达目标正方形。在每一步中，我们可以走到网格中上，下，左，右相邻的正方形，该正方形不在给定的阻止单元列表中。

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

因此，如果输入就像阻塞= [[0,1]，[1,0]]，源= [0,0]，目标= [0,3]，那么输出将为False

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

• 阻止的：=设置所有阻止的单元格的集合

• 定义一个方法dfs()，将采用x，y，目标和可见

• 如果(x,y)不在网格范围内或(x,y)处于阻塞状态或(x,y)处于可见状态，则

• 返回假

• 
  

• 将(x,y)添加到可见

• 如果看到的大小> 20000或(x,y)是目标，则

• 返回真

• 返回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（源[0]，源[1]，目标，空集）和dfs（目标[0]，目标[1]，源，空集）

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

示例

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]))

输入值

[[0,1],[1,0]], [0,0], [0,3]

输出结果

False