如何判断二维数组中两点间是否存在长度≤X的路径（JS实现）

要解决这个问题，BFS（广度优先搜索）是最优选择——它天然适合寻找最短路径，我们可以通过追踪每一步的路径长度，直接判断目标点是否能在指定长度内到达。以下是适配你这种方向连接结构的具体实现：

核心思路 #

每个节点的con数组定义了它能往哪些方向走，但必须满足双向连通：比如当前节点允许向下走（bottom），那么下方的节点必须允许向上走（top），才算真正连通。我们用BFS按层遍历，每一层对应路径长度，一旦遍历到目标点，就可以直接对比当前路径长度和给定的pathLength。

完整代码实现 #

function validPath(arr, pathLength, startPos, endPos) {
    // 方向映射：键是当前节点的方向，值是[坐标偏移, 相邻节点需要的反向方向]
    const dirMap = {
        top: [-1, 0, "bottom"],
        bottom: [1, 0, "top"],
        left: [0, -1, "right"],
        right: [0, 1, "left"]
    };

    const rows = arr.length;
    const cols = arr[0].length;
    // 初始化访问标记数组，避免重复遍历节点
    const visited = Array(rows).fill(false).map(() => Array(cols).fill(false));
    // 队列元素格式：[y坐标, x坐标, 当前路径长度]
    const queue = [[startPos[0], startPos[1], 0]];
    visited[startPos[0]][startPos[1]] = true;

    while (queue.length > 0) {
        const [y, x, currentLen] = queue.shift();

        // 到达目标点，判断当前路径长度是否符合要求
        if (y === endPos[0] && x === endPos[1]) {
            return currentLen <= pathLength;
        }

        // 如果当前长度已经等于pathLength，再走一步就超了，跳过后续处理
        if (currentLen >= pathLength) {
            continue;
        }

        // 遍历当前节点的所有可连接方向
        const currentNode = arr[y][x];
        for (const dir of currentNode.con) {
            const [dy, dx, reverseDir] = dirMap[dir];
            const newY = y + dy;
            const newX = x + dx;

            // 检查相邻节点是否在数组范围内、未被访问，且反向连通
            if (newY >= 0 && newY < rows && newX >=0 && newX < cols) {
                if (!visited[newY][newX] && arr[newY][newX].con.includes(reverseDir)) {
                    visited[newY][newX] = true;
                    queue.push([newY, newX, currentLen + 1]);
                }
            }
        }
    }

    // 遍历完所有可达节点都没找到目标点
    return false;
}

// 测试用例
let arr = [
    [{ id: 1, con: ["bottom", "right"] }, { id: 3, con: ["left"] }, { id: 8, con: ["right"] }],
    [{ id: 4, con: ["top", "bottom"] }, { id: 9, con: [] }, { id: 5, con: [] }],
    [{ id: 6, con: ["top", "right"] }, { id: 7, con: ["left", "right"] }, { id: 2, con: ["left"] }],
];

console.log(validPath(arr, 2, [0, 0], [2, 1])); // false：最短路径长度是3
console.log(validPath(arr, 3, [0, 0], [2, 1])); // true：刚好等于最短路径长度
console.log(validPath(arr, 5, [0, 0], [2, 1])); // true：3 ≤5，符合要求

代码解释 #

1. 方向映射：dirMap把每个方向转换成坐标偏移，同时记录相邻节点需要的反向方向，确保双向连通。
2. 访问标记：visited数组防止重复遍历同一个节点，避免死循环和无效计算。
3. 队列处理：每次从队列取出节点，先判断是否是目标点；如果当前路径长度已经达到pathLength，就不再继续探索该节点的邻居，因为再走一步就会超出限制。
4. 连通性检查：遍历当前节点的每个方向时，不仅要检查相邻节点是否在数组范围内，还要确认相邻节点允许反向连接，这样才是有效的路径。

测试用例说明 #

从[0,0]（id:1）到[2,1]（id:7）的最短路径是：
[0,0] → [1,0]（id:4） → [2,0]（id:6） → [2,1]（id:7），路径长度为3。所以：

• 当pathLength=2时，无法到达，返回false；
• 当pathLength≥3时，可以到达，返回true。

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