【广度优先搜索】1976: 仙岛求药

### 仙岛求药问题分析 此问题是典型的最短路径问题，可以通过广度优先搜索算法（BFS）解决。地图中的每一个位置可以用二维坐标表示，障碍物代表不可通过的位置，而起点到终点的距离则定义为所经过的安全方格数。 #### 输入与输出描述 输入通常包括以下几个部分： - 地图大小 $ M \times N $ - 起点和终点的坐标 $(x_s, y_s)$ 和 $(x_e, y_e)$ - 地图矩阵，其中 `0` 表示可通过区域，`1` 表示障碍物 输出为目标路径长度或者无法到达的情况提示。 --- ### 解决方案设计 以下是基于 BFS 的解决方案： ```python from collections import deque def bfs_shortest_path(grid, start, end): rows, cols = len(grid), len(grid[0]) visited = [[False for _ in range(cols)] for _ in range(rows)] queue = deque() queue.append((start[0], start[1], 0)) # (row, col, distance) directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右下左上 while queue: r, c, dist = queue.popleft() if (r, c) == end: return dist for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and grid[nr][nc] == 0: visited[nr][nc] = True queue.append((nr, nc, dist + 1)) return -1 # 如果无法到达，则返回 -1 # 示例调用 if __name__ == "__main__": grid_example = [ [0, 1, 0, 0], [0, 0, 0, 1], [1, 1, 0, 0], [0, 0, 0, 0] ] start_point = (0, 0) end_point = (3, 3) result = bfs_shortest_path(grid_example, start_point, end_point) print(f"Shortest path length: {result}") ``` 上述代码实现了 BFS 算法的核心逻辑[^2]。它利用队列存储当前节点及其距离，并逐步扩展至相邻节点直到找到目标节点为止。 --- ### 关键点解析 1. **初始化访问标记数组** 使用布尔型二维列表记录已访问过的节点，防止重复计算并优化性能[^3]。 2. **方向向量** 定义四个基本移动方向 `(右, 下, 左, 上)` 来遍历邻居节点[^4]。 3. **边界条件判断** 在每次尝试移动前验证新位置是否越界以及是否存在障碍物[^5]。 4. **终止条件** 当首次遇到目标节点时立即返回其对应的步数作为结果；如果穷尽所有可能性仍未抵达目的地，则返回 `-1` 表明无解[^6]。 --- ### 时间复杂度与空间复杂度 时间复杂度：$ O(M \cdot N) $，因为最多会访问网格中的每个单元一次。 空间复杂度：同样为 $ O(M \cdot N) $，主要来源于辅助数据结构如队列和访问状态表。 --- 问题