找到从 0,0 开始的 4x4 矩阵中的每一条路径，该路径接触每个单元格一次并且不会重新访问任何单元格？

Question

我试图生成通过 NxN 矩阵的所有路径，这些路径从 (0,0) 开始接触每个单元格一次，而无需重新访问任何单元格。因此，4x4 矩阵中的每条路径都有 16 步长。路径的每一步只能向任意方向移动 1 个单元格，包括对角线方向。我尝试使用基于 DFS 或 BFS 的方法以不同的方式编写此内容几个小时，但到目前为止尚未成功。我在打字稿工作。任何对图算法有更好掌握的人都可以帮我吗？

这是我到目前为止所拥有的，但其他人可能会更好从头开始，因为这几乎不起作用。

type Position = [number, number];

// Define the directions for moving (including diagonals)
const directions: Position[] = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1, -1],  [1, 0],  [1, 1]
];

// Checks if a given position is valid within an NxN matrix
function isValid(n: number, x: number, y: number, visited: boolean[][]): boolean {
  return x >= 0 && y >= 0 && x < n && y < n && !visited[x][y];
}

function bfs(n: number): void {
    let visited: boolean[][] = Array(4).fill(false).map(
      () => Array(4).fill(false)
    );

    let queue: { path: Position[], visited: boolean[][] }[] = [];
    queue.push({ path: [[0, 0]], visited: visited }); // Start with the top-left corner

    while (queue.length > 0) {
      let current = queue.shift()!; // Dequeue current position
      let [x, y] = current.path[current.path.length - 1]; // Get current position
      if (current.path.length === 16) {
        // We have visited all nodes, print the path
        console.log(current.path);
        continue;
      }
      for (let [dx, dy] of directions) {
        let newX = x + dx;
        let newY = y + dy;
        if (isValid(n, newX, newY, current.visited)) {
          let newPath: Position[] = [...current.path, [newX, newY]]; // Extend the path
          let newVisited: boolean[][] = current.visited.map(row => row.slice()); // Copy visited array
          newVisited[newX][newY] = true; // Mark the new position as visited
          queue.push({ path: newPath, visited: newVisited }); // Enqueue new path
        }
      }
    }
}

bfs(4);

Answer 1

更多信息请立即访问

并学习有用的信息