資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python大型迷宮逃脫
假設我們有一個網格，有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) 是 target，則
返回 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, 空集) 且 dfs(target[0], target[1], source, 空集)
讓我們看看下面的實現以更好地理解：
示例
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
更新於：2020年6月4日
瀏覽量：353
廣告