Python中含不可通行瓦片的2D地图类曼哈顿距离最短路径求解

对于你描述的无权2D网格路径搜索场景，有两种最常用的实现方案：

方案1：BFS（广度优先搜索）—— 最通用的无权最短路径实现 #

BFS是无权网格最短路径计算的标准实现，无需额外依赖，手动实现逻辑简单，适配你的嵌套列表格式：

• 仅搜索值为True的可通行单元格，自动跳过False的障碍单元格
• 默认支持上下左右四个方向移动，如有斜向移动需求可自行扩展方向配置
• 首次到达终点时的路径就是最短路径，可按需返回路径长度或完整路径节点

示例代码（仅返回最短路径长度）：

from collections import deque

def shortest_path_length(grid, start, end):
    # grid：嵌套布尔列表，start/end：(行索引, 列索引)格式的坐标
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    # 四个移动方向：上、下、左、右
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    q = deque()

    # 边界校验
    if not (0<=start[0]<rows and 0<=start[1]<cols and grid[start[0]][start[1]]):
        return -1 # 起点非法/不可通行
    if not (0<=end[0]<rows and 0<=end[1]<cols and grid[end[0]][end[1]]):
        return -1 # 终点非法/不可通行
    if start == end:
        return 0

    q.append((start[0], start[1], 0))
    visited[start[0]][start[1]] = True
    while q:
        x, y, dist = q.popleft()
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 0<=nx<rows and 0<=ny<cols and not visited[nx][ny] and grid[nx][ny]:
                if (nx, ny) == end:
                    return dist + 1
                visited[nx][ny] = True
                q.append((nx, ny, dist+1))
    return -1 # 两点之间无可达路径

如果你需要返回完整路径而不是仅长度，可以在队列中额外存储当前走过的路径列表，或者单独维护父节点坐标映射，最后从终点反向回溯即可得到完整路径。

方案2：A* 算法 —— 大尺寸网格优化方案 #

如果你的网格尺寸较大，BFS全局搜索效率不足，可以采用A*算法，以曼哈顿距离作为启发函数，能大幅缩小搜索范围，搜索速度远快于BFS，最终得到的结果同样是最短路径。

现成库调用方案 #

如果不想手动实现基础逻辑，可以直接用第三方库的封装接口：

• networkx：先将可通行单元格转为图节点、相邻可通行单元格之间加边，直接调用nx.shortest_path_length或nx.shortest_path即可得到结果
• pathfinding：专门面向网格路径搜索的第三方库，原生支持布尔格式的网格输入，内置BFS、A*、Dijkstra等多种算法，调用门槛更低

内容的提问来源于stack exchange，提问作者Daniel