首页leetcode490

leetcode490

时间: 2025-02-18 20:52:38 浏览: 42

### LeetCode 490 题目解析 #### 题目描述 LeetCode 第 490 题名为《迷宫》[^6]。题目给定一个由 `0` 和 `1` 组成的二维网格，其中 `0` 表示可以通过的空间，而 `1` 则表示障碍物。起点位于左上角 `(0, 0)`，终点位于右下角 `(m-1, n-1)`。需要判断是否存在一条路径可以从起点到达终点。 #### 解决方案概述该问题可以使用广度优先搜索算法（BFS）来解决。通过 BFS 可以有效地遍历所有可能的路径并找到最短的一条通往目标位置的路。如果能够成功抵达，则返回 True；反之则返回 False。 #### 实现细节为了实现上述思路，在 Python 中定义了一个辅助函数 `_bfs()` 来执行具体的 BFS 过程： ```python from collections import deque def hasPath(maze, start, destination): directions = [(0, 1), (0, -1), (-1, 0), (1, 0)] m, n = len(maze), len(maze[0]) queue = deque([start]) visited = set() visited.add((start[0], start[1])) while queue: curr_x, curr_y = queue.popleft() if [curr_x, curr_y] == destination: return True for dx, dy in directions: nx, ny = curr_x, curr_y # Roll until hitting wall or boundary while 0 <= nx + dx < m and 0 <= ny + dy < n 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 ``` 此代码片段展示了如何利用队列来进行层次化探索，并记录访问过的节点防止重复计算。每当遇到新的未被标记的位置时就将其加入到待处理列表中继续扩展直到发现目的地或者穷尽所有可能性为止。

阅读全文