如何在JavaScript中找出多行数组构成的所有合法遍历路径？

先把问题里的规则明确梳理清楚，避免歧义：

• 路径必须从第0行的任意单元格开始
• 移动方向必须交替：如果上一次是水平移动（同一行内跳转），下一次只能是垂直移动（同一列内跳转），反之亦然；初始状态下（第一步移动）可以选水平或垂直（若要严格遵循「先水平遍历」，后面会说怎么调整）
• 路径里不能重复访问同一个单元格（比如不能同时出现00(E9)两次）
• 路径里不能出现重复的值（比如选了E9之后，所有值为E9的单元格都不能再选）
• 移动时可以跳过当前行/列的其他单元格，直接跳转到符合条件的目标（不需要相邻移动）

算法核心思路 #

用**深度优先搜索（DFS）**来遍历所有可能的路径最合适——这种方法能探索所有符合条件的分支，直到无法继续扩展为止。核心是跟踪每个遍历状态的关键信息：当前位置、已访问的单元格、已使用的值、上一次的移动方向，以及当前路径。

JavaScript代码实现 #

先把你的数据转换成更易操作的二维数组，再实现DFS逻辑：

// 原始数据
const data = {
  r0: ["E9", "55", "1C"],
  r1: ["1C", "E9", "E9"],
  r2: ["BD", "1C", "55"]
};

// 转换为二维数组，rows[行索引][列索引]直接取值
const rows = Object.values(data);
const totalRows = rows.length;
const totalCols = rows[0].length;

// 存储所有符合条件的路径
const allValidPaths = [];

// 遍历第0行的所有单元格作为起点
for (let col = 0; col < totalCols; col++) {
  const startRow = 0;
  const startValue = rows[startRow][col];
  // 记录已访问的单元格（用"行,列"字符串作为唯一标识）
  const visitedCells = new Set([`${startRow},${col}`]);
  // 记录已使用的值
  const usedValues = new Set([startValue]);
  // 初始路径
  const currentPath = [`${startRow}${col}(${startValue})`];
  
  // 启动DFS，初始状态没有上一次移动方向
  dfs(startRow, col, visitedCells, usedValues, 'none', currentPath);
}

/**
 * 深度优先搜索函数
 * @param {number} row 当前所在行
 * @param {number} col 当前所在列
 * @param {Set} visited 已访问的单元格集合
 * @param {Set} used 已使用的值集合
 * @param {string} lastDir 上一次移动方向：'horizontal'/'vertical'/'none'
 * @param {string[]} path 当前路径
 */
function dfs(row, col, visited, used, lastDir, path) {
  let nextPossibleMoves = [];

  // 确定当前可以进行的移动类型
  if (lastDir === 'none' || lastDir === 'vertical') {
    // 上一次是垂直移动或初始状态，当前可以水平移动（同一行内）
    for (let c = 0; c < totalCols; c++) {
      if (c === col) continue; // 跳过当前单元格
      const cellKey = `${row},${c}`;
      const value = rows[row][c];
      // 检查单元格未被访问且值未被使用
      if (!visited.has(cellKey) && !used.has(value)) {
        nextPossibleMoves.push({
          type: 'horizontal',
          newRow: row,
          newCol: c,
          val: value
        });
      }
    }
  }

  if (lastDir === 'none' || lastDir === 'horizontal') {
    // 上一次是水平移动或初始状态，当前可以垂直移动（同一列内）
    for (let r = 0; r < totalRows; r++) {
      if (r === row) continue; // 跳过当前单元格
      const cellKey = `${r},${col}`;
      const value = rows[r][col];
      if (!visited.has(cellKey) && !used.has(value)) {
        nextPossibleMoves.push({
          type: 'vertical',
          newRow: r,
          newCol: col,
          val: value
        });
      }
    }
  }

  // 如果没有可移动的下一步，当前路径就是一条有效路径
  if (nextPossibleMoves.length === 0) {
    allValidPaths.push(path.join(', '));
    return;
  }

  // 遍历所有可能的下一步，递归探索
  for (const move of nextPossibleMoves) {
    // 复制状态，避免修改原状态（保证DFS分支的独立性）
    const newVisited = new Set(visited);
    const newUsed = new Set(used);
    const newPath = [...path];
    
    const newCellKey = `${move.newRow},${move.newCol}`;
    newVisited.add(newCellKey);
    newUsed.add(move.val);
    newPath.push(`${move.newRow}${move.newCol}(${move.val})`);
    
    // 递归调用，传入新的状态
    dfs(move.newRow, move.newCol, newVisited, newUsed, move.type, newPath);
  }
}

// 输出所有有效路径
allValidPaths.forEach(path => console.log(path));

调整规则的小技巧 #

如果需要严格遵循「先水平遍历」（即第一步必须是水平移动，不能先垂直），只需要修改DFS中初始状态的移动权限：
把lastDir === 'none'时的垂直移动分支注释掉即可，也就是：

// 注释掉这部分，限制初始状态只能水平移动
// if (lastDir === 'none' || lastDir === 'horizontal') {
//   ...
// }

这样所有路径的第一步都会是第0行内的水平跳转。

结果说明 #

运行代码后，你会得到所有符合条件的路径，每条路径都会在无法继续扩展时停止，和你给出的示例格式完全一致。

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