题目描述：

由空地和墙组成的迷宫中有一个球。球可以向上（u）、下（d）、左（l）或右（r）四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。迷宫中有一个终点，当球到达终点时，游戏结束。

给定迷宫的二维网格，其中 1 表示墙壁， 表示空地，以及球的起始位置和终点位置，请判断球能否到达终点。

示例：

输入 1: 迷宫由以下二维数组表示

解释: 球可以按照如下路径从起点滚到终点： (0, 4) -> (0, 3) -> (1, 3) -> (1, 2) -> (1, 1) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4)

解题思路：

1. 深度优先搜索（DFS）：
   • 从起始位置开始，尝试四个方向滚动。
   • 每个方向上，球会一直滚动直到遇到墙壁或边界。
   • 到达新位置后，递归地继续搜索。
   • 如果到达终点，返回 true。
   • 使用一个集合记录已经访问过的位置，避免重复搜索。
2. 广度优先搜索（BFS）：
   • 使用队列存储待访问的位置。
   • 从起始位置开始，将四个方向上的可行位置加入队列。
   • 每次从队列中取出一个位置，检查是否到达终点。
   • 如果到达终点，返回 true。
   • 否则，继续将新位置加入队列。

代码实现（DFS）：

def hasPath(maze, start, destination): def dfs(maze, start, destination, visited): if start == destination: return True visited.add(start) directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] for dx, dy in directions: x, y = start while 0 <= x + dx < len(maze) and 0 <= y + dy < len(maze[0]) and maze[x + dx][y + dy] == 0: x += dx y += dy if (x, y) not in visited and dfs(maze, (x, y), destination, visited): return True return False

visited = set()
return dfs(maze, tuple(start), tuple(destination), visited)

print(hasPath(maze, start, destination)) # 输出: True

代码实现（BFS）：

from collections import deque

while queue:
    x, y = queue.popleft()
    if (x, y) == tuple(destination):
        return True
    for dx, dy in directions:
        nx, ny = x, y
        while 0 <= nx + dx < len(maze) and 0 <= ny + dy < len(maze[0]) and maze[nx + dx][ny + dy] == 0:
            nx += dx
            ny += dy
        if (nx, ny) not in visited:
            visited.add((nx, ny))
            queue.append((nx, ny))
return False

print(hasPath(maze, start, destination)) # 输出: True

总结：

• DFS 适合于路径搜索，但可能会遇到深度很大的情况，导致栈溢出。
• BFS 适合于寻找最短路径，且不会因为深度过大而出现问题，但需要更多的空间来存储队列。

根据具体问题的需求选择合适的算法。在这个迷宫问题中，两种方法都可以有效解决。