基于二维列表构建图：连通x元素分组与组间最短路径求解

1. 连通X分组实现 #

这里默认连通规则为四连通（上下左右相邻即视为连通，如需包含斜向相邻可改成八连通），可通过DFS或BFS实现，步骤如下：

• 提前创建和原二维数组尺寸相同的访问标记数组，所有元素初始为false，用于标记已经被归入分组的x坐标，避免重复统计
• 逐行逐列遍历二维数组的每个坐标(i,j)：
  • 若当前坐标值为x且未被访问过，说明找到新分组的起始点，新建空分组存储当前分组的所有坐标
  • 以当前坐标为起点执行DFS/BFS：
    • 每遍历到一个值为x且未被访问的坐标，就将其加入当前分组，同时将访问标记数组对应位置设为true
    • 遍历完成后将当前分组存入总分组列表

附JS示例实现代码：

function groupX(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    const visited = Array.from({length: rows}, () => Array(cols).fill(false));
    const groups = [];
    // 四连通方向
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 'x' && !visited[i][j]) {
                const group = [];
                const queue = [[i,j]];
                visited[i][j] = true;
                // BFS遍历
                while (queue.length) {
                    const [x, y] = queue.shift();
                    group.push(`(${x},${y})`);
                    for (const [dx, dy] of dirs) {
                        const nx = x + dx;
                        const ny = y + dy;
                        if (nx >=0 && nx < rows && ny >=0 && ny < cols && grid[nx][ny] === 'x' && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            queue.push([nx, ny]);
                        }
                    }
                }
                groups.push(group);
            }
        }
    }
    return groups;
}
// 测试示例数据
const a = [
   ["x", "x", 0,  0, "x", "x"],
   [ 0,   0,  0,  0, "x", "x"],
   ["x", "x", 0,  0,  0,  "x"],
   ["x", "x", 0,  0,  0,   0 ]
];
console.log(groupX(a)) 

上述代码运行后输出的分组结果和你给出的示例完全一致。

2. 两个分组之间的最短路径计算 #

根据使用场景分为两种常见计算方式：

场景1：纯坐标最短距离（不考虑网格障碍物） #

直接计算所有坐标对的曼哈顿距离取最小值即可：

• 枚举分组A的所有坐标，枚举分组B的所有坐标
• 计算每对坐标的曼哈顿距离：|x1 - x2| + |y1 - y2|
• 所有计算结果中的最小值就是两个分组的最短距离

场景2：网格可通行最短路径（只能走值为0的格子，上下左右移动，每步算1距离） #

用多源BFS实现效率最高：

• 将分组A的所有坐标作为BFS的初始起点，全部加入队列，对应坐标距离标记为0，同时标记已访问
• 按层执行BFS遍历，每向外扩展一层距离加1
• 当第一次遍历到属于分组B的坐标时，当前的距离就是两个分组的最短路径

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