难度: Medium
Submission
运行时间: 42 ms
内存: 17.2 MB
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n = len(maze), len(maze[0])
visited = [[False] * n for _ in range(m)]
directions = (
(1, 0), (-1, 0),
(0, -1), (0, 1)
)
def dfs(i, j) -> bool:
if i == destination[0] and j == destination[1]:
return True
visited[i][j] = True
for dx, dy in directions:
# initial starting point
new_i, new_j = i, j
while 0 <= new_i + dx < m and 0 <= new_j + dy < n and maze[new_i + dx][new_j + dy] == 0:
# keep going in the same direction
new_i += dx
new_j += dy
if not visited[new_i][new_j]:
if dfs(new_i, new_j):
return True
return False
return dfs(*start)
Explain
这个题解使用深度优先搜索（DFS）来判断从起点是否能到达终点。具体来说，从起点开始，沿着四个方向（上下左右）一直滚动，直到撞到墙或者到达边界。每个位置只访问一次，如果滚动到终点则返回 true，否则继续尝试其他方向。如果所有方向都尝试过仍无法到达终点，则返回 false。
时间复杂度: O(mn * max(m, n))
空间复杂度: O(mn)
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n = len(maze), len(maze[0])
visited = [[False] * n for _ in range(m)]
directions = (
(1, 0), (-1, 0),
(0, -1), (0, 1)
)
def dfs(i, j) -> bool:
# 如果到达终点，返回 True
if i == destination[0] and j == destination[1]:
return True
# 标记当前位置已访问
visited[i][j] = True
# 尝试沿四个方向滚动
for dx, dy in directions:
# 初始滚动位置
new_i, new_j = i, j
# 沿当前方向一直滚动直到撞墙或出界
while 0 <= new_i + dx < m and 0 <= new_j + dy < n and maze[new_i + dx][new_j + dy] == 0:
new_i += dx
new_j += dy
# 如果滚动到的新位置没有访问过，则递归访问它
if not visited[new_i][new_j]:
if dfs(new_i, new_j):
return True
# 如果所有方向都无法到达终点，返回 False
return False
# 从起点开始搜索
return dfs(*start)
Explore
在这个迷宫问题中，选择一直滚动到撞墙或出界而不是每次只移动一步的主要原因是，这种滚动方式可以更有效地模拟球在迷宫中的实际移动。实际上，球在没有障碍物的情况下会持续滚动直到撞到墙壁。这种方法减少了必须考虑的节点数量，因为它跳过了在直线路径上的多个中间步骤，从而提高了搜索效率。此外，这也确保了算法更快地跨越空旷区域，减少了递归深度，从而在一定程度上减少了栈溢出的风险。
在DFS递归中，如果递归调用返回true，意味着从当前位置到终点已经找到了一条有效路径。因此，可以立即断定整个DFS返回true，并结束所有进一步的搜索。这里并没有省略回溯机制，实际上这是回溯的一部分。当递归调用找到一个成功的路径时，它会逐层返回true，递归地传播这个成功的结果。如果没有找到有效路径，递归调用会返回false，然后尝试其他可能的路径。这确保了即使部分路径失败，搜索也能继续进行，直到找到有效路径或确认没有路径存在。
该算法考虑了起点和终点位置相同的情况，因为它首先检查起点是否即为终点，如果是，则立即返回true。然而，对于迷宫中的所有位置都是墙壁这种情况，根据题解的代码实现，如果起点是墙，则函数将不会进行任何有效的DFS调用，因此会返回false。但如果没有明确检查起点是否为墙，这可能需要在实际应用中额外验证确保输入数据的有效性。
在题解中的DFS实现里，每次滚动停止前的检查确保了我们不会越界。在`while`循环中，条件`0 <= new_i + dx < m`和`0 <= new_j + dy < n`以及`maze[new_i + dx][new_j + dy] == 0`被用来保证不会滚动到墙上或出界。因此，这样的检查是正确的并且防止了对边界的错误判断，它确保了只有在滚动到有效的空白位置时才停止。