题目描述：

由空地和墙组成的迷宫中有一个球。球可以向上（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 适合于寻找最短路径，且不会因为深度过大而出现问题，但需要更多的空间来存储队列。

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

好的，我们来详细讨论一下 LeetCode 上的第 489 题：Robot Room Cleaner。

题目描述

这道题要求我们模拟一个机器人在一个未知的房间内进行清洁的过程。房间的布局是未知的，机器人只能通过有限的方向移动（通常是上、下、左、右），并且机器人不能回到已经清洁过的位置。

机器人有一个 clean 方法用来清洁当前位置，以及一个 move 方法用来移动到下一个位置。如果移动失败（比如遇到了墙壁），move 方法会返回 false。机器人还有一个 turnLeft 和 turnRight 方法用来改变方向。

解题思路

这道题可以使用深度优先搜索（DFS）来解决这个问题。关键点在于如何避免重复访问已经清洁过的位置，以及如何确保机器人能够回到出发点。

1. 方向控制：定义一个方向数组，比如 [(0, 1), (1, 0), (0, -1), (-1, 0)]，分别代表上、右、下、左四个方向。
2. 状态记录：使用一个集合来记录已经清洁过的位置。
3. 回溯：在每次移动到一个新位置后，进行清洁，并递归地探索其他方向。探索完所有方向后，需要回到上一个位置。

代码实现

以下是一个 Python 示例代码，假设机器人类已经定义好了 clean, move, turnLeft, turnRight 方法。

class Solution: def cleanRoom(self, robot): def go_back(): robot.turnRight() robot.turnRight() robot.move() robot.turnRight() robot.turnRight()

    def dfs(x, y, d):
        robot.clean()
        visited.add((x, y))

        for i in range(4):
            new_d = (d + i) % 4
            new_x, new_y = x + directions[new_d][0], y + directions[new_d][1]

            if (new_x, new_y) not in visited and robot.move():
                dfs(new_x, new_y, new_d)
                go_back()

            robot.turnRight()

    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = set()
    dfs(0, 0, 0)

def move(self):
    pass

def turnLeft(self):
    pass

def turnRight(self):
    pass

详细解释

1. go_back 函数：这个函数用于让机器人回到上一个位置。具体操作是先转180度，然后移动一步，再转回原来的方向。
2. dfs 函数：这是一个深度优先搜索函数，参数 (x, y, d) 分别表示当前的位置和方向。
   • 首先清洁当前位置，并将当前位置加入 visited 集合。
   • 然后尝试四个方向（通过循环和方向数组 directions 实现）。
   • 如果新位置没有被访问过且可以移动，递归调用 dfs。
   • 每次尝试新方向前，先右转，以便下一次循环时尝试下一个方向。
3. 主函数：初始化方向数组和访问集合，从 (0, 0, 0)（即起始位置和向上方向）开始进行深度优先搜索。

注意事项

• 机器人类的具体实现细节（如 clean, move, turnLeft, turnRight 方法）需要根据题目提供的接口来调整。
• 这道题的关键在于理解和实现回溯过程，确保机器人能够回到出发点。

希望这个详细的解答能帮助你理解并解决这道题目。如果有更多问题，欢迎继续提问！

《Zuma Game》（祖玛游戏）是 LeetCode 上的第 488 题，这是一个中等难度的题目，主要考察的是深度优先搜索（DFS）和广度优先搜索（BFS）的算法应用。

题目描述

在一个二维的平面中，有一些彩球按顺序排列成一行，你需要通过射出彩球来消除这些彩球。当三个或更多相同颜色的彩球相连时，这些彩球会被消除。你需要找到消除所有彩球所需的最少射击次数。

输入：

• board：一个字符串，表示初始彩球的排列。
• hand：一个字符串，表示你手中持有的彩球。

输出：

• 返回消除所有彩球所需的最少射击次数。如果无法消除所有彩球，则返回 -1。

示例

输入：board = "WRRBBW", hand = "RB" 输出：-1 解释：无法通过手中的彩球消除所有彩球。

1. 射击手中的 'R' 到位置 3，使得 "WWRRBBWW" 变为 "WWRRRBBWW"。
2. 射击手中的 'B' 到位置 6，使得 "WWRRRBBWW" 变为 "WWRRRBBBW"。 这时，三个 'R' 和三个 'B' 相连，被消除，剩下的 "WWW" 也会被自动消除。

   解题思路

深度优先搜索（DFS）：

• 从左到右遍历 board，找到第一个可以插入的位置。
• 尝试将手中的彩球插入到该位置，并递归地进行下一步搜索。
• 每次插入后，检查是否有连续的三个或更多相同颜色的彩球，如果有则消除它们，并继续递归搜索。
• 记录每次搜索的结果，找到最少射击次数。