数据结构
网络
关系数据库管理系统 (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
广告