?LeetCode解法汇总874. 模拟行走机器人

**模拟行走机器人的解决方案**

在本文中，我们将讨论如何使用算法来模拟一个行走的机器人。这个问题涉及到机器人从起点移动到终点，遵循一定的规则和限制。

**问题描述**

假设我们有一个机器人，它可以向上、下、左、右四个方向移动一步。机器人不能回头，也就是说它不能移动到已经走过的路径上。给定起点和终点，我们需要找到从起点移动到终点所需的最短距离。

**解决方案**

我们将使用广度优先搜索（BFS）算法来解决这个问题。BFS是一种图论算法，用于在无权图中寻找从起点到任意目标顶点的最短路径。

###代码实现

from collections import dequedef robotWalk(start, end):
 # 定义四个方向 directions = [(0,1), (0, -1), (1,0), (-1,0)]
 # 创建一个队列，用于存储待处理的顶点 queue = deque([(start,0)]) # (顶点，距离)
 # 创建一个集合，用于存储已经访问过的顶点 visited = set([start])
 while queue:
 vertex, dist = queue.popleft()
 if vertex == end:
 return dist for direction in directions:
 new_vertex = (vertex[0] + direction[0], vertex[1] + direction[1])
 # 检查新顶点是否已经访问过或超出边界 if new_vertex not in visited and0 <= new_vertex[0] < 10 and0 <= new_vertex[1] < 10:
 queue.append((new_vertex, dist +1))
 visited.add(new_vertex)
 return -1 # 如果无法到达终点，返回-1# 测试start = (0,0)
end = (9,9)
print(robotWalk(start, end)) # 输出：18