大きな迷路のPythonを脱出する

グリッドがあり、100万行と100万列があり、ブロックされたセルのリストも1つあるとします。次に、ソーススクエアから開始し、ターゲットスクエアに到達します。それぞれの動きで、ブロックされたセルの指定されたリストにないグリッド内の上下左右に隣接する正方形まで歩くことができます。

一連の移動で目標のマスに到達できるかどうかを確認する必要があります。

したがって、入力がblocked =[[0,1]、[1,0]]、source =[0,0]、target =[0,3]のような場合、出力はFalseになります

これを解決するには、次の手順に従います-

• ブロックされた：=すべてのブロックされたセルのセットを作成する

• 1つのメソッドdfs（）を定義します。これは、x、y、targetを取り、表示されます

• （x、y）がグリッドの範囲内にないか、（x、y）がブロックされているか、（x、y）が表示されている場合、

  • falseを返す

  • 
    

• （x、y）を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、見た）

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

入力

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

出力

False