【力扣每日一题】2023.7.19 模拟行走机器人

**力扣每日一题**

**2023.7.19 模拟行走机器人**

在一个二维平面中，存在一个机器人，它可以向上、下、左、右移动一步。给定一个初始坐标和一个目标坐标，我们需要判断是否能够从起点到达终点。

**示例1:**

输入：`start = [0,0], end = [3,1]`
输出：`true`

**示例2:**

输入：`start = [0,0], end = [-2,-2]`
输出：`false`

**示例3:**

输入：`start = [0,0], end = [4,5]`
输出：`true`

**示例4:**

输入：`start = [0,0], end = [1,1]`
输出：`true`

**示例5:**

输入：`start = [0,0], end = [-3,-2]`
输出：`false`

**思路和解法**

这个问题可以使用广度优先搜索（BFS）来解决。我们首先将起点加入到队列中，然后开始遍历邻居节点，直到找到终点或队列为空。

from collections import dequedef is_valid(x, y):
 return0 <= x < len(grid[0]) and0 <= y < len(grid)

def robot_walk(grid, start, end):
 if not grid or not grid[0]:
 return False rows, cols = len(grid), len(grid[0])
 # 将起点加入到队列中 queue = deque([(start[0], start[1])])
 # 标记已访问的节点 visited = {(start[0], start[1]): True}
 while queue:
 x, y = queue.popleft()
 if [x, y] == end:
 return True for dx, dy in [(1,0), (-1,0), (0,1), (0, -1)]:
 nx, ny = x + dx, y + dy # 检查是否有效 if is_valid(nx, ny) and not visited.get((nx, ny)):
 queue.append((nx, ny))
 visited[(nx, ny)] = True return False# 测试用例grid = [
 [0,0,0],
 [0,1,0],
 [0,0,0]
]

print(robot_walk(grid, [0,0], [2,2])) # True