c++ - 递归确定游戏板上所有字段的最小移动

Question

我正在尝试更好地理解递归，所以我决定编写一个程序来确定 N * N 游戏板上所有字段的最短路径，使用递归（我知道 BFS 在这里会更快，这只是为了学习）：

void visit(int x, int y, int moves)
{
  if (x < 0 || x >= n || y < 0 || y >= n) {
    return; // out of board
  } else if (board[y][x] != -1) {
    // already visited, check if path is shorter
    if (moves < board[y][x]) board[y][x] = moves;
    return;
  } else {
    // first time visiting
    board[y][x] = moves;

    visit(x + 1, y, moves + 1); // right
    visit(x, y + 1, moves + 1); // down
    visit(x, y - 1, moves + 1); // up
    visit(x - 1, y, moves + 1); // left
  }
}
# called with visit(0, 0, 0), so it should be able to start at any field

但是，对于 3x3 板，它会产生以下板：

0 1 2
1 2 3
6 5 4

前两行是对的，但最后一行（最后一行的最后一列除外）是错误的。它应该是：

0 1 2
1 2 3
2 3 4

这是一个 4x4 板：

0 1 2 3
1 2 3 4
12 9 6 5
13 8 7 6

Answer 1

else if (board[y][x] != -1) {
    // already visited, check if path is shorter
    if (moves < board[y][x]) board[y][x] = moves;
    return;
}

回到这里是错误的。您刚刚降低了这条路径的分数 - 该区域中可能还有其他路径可以降低分数：

void visit(int x, int y, int moves)
{
  if (x < 0 || x >= n || y < 0 || y >= n) {
    return; // out of board
  } else if (board[y][x] == -1 || moves < board[y][x]) {
    // first time visiting
    board[y][x] = moves;

    visit(x + 1, y, moves + 1);
    visit(x, y + 1, moves + 1);
    visit(x, y - 1, moves + 1);
    visit(x - 1, y, moves + 1);
  } else {
    return;
  }
}

按预期工作。

Answer 2

这会奏效。

void visit(int x, int y, int moves)
{
  if (x < 0 || x >= n || y < 0 || y >= n) {
    return; // out of board
  } 
  else if ( board[y][x] == -1 || moves < board[y][x]) 
  {
    board[y][x] = moves;
    visit(x + 1, y, moves + 1);
    visit(x, y + 1, moves + 1);
    visit(x, y - 1, moves + 1);
    visit(x - 1, y, moves + 1);
  }
}

此外，如果你用 (2*n-2) 而不是 -1 来初始化 board 的每个元素，你可以放弃 ( board[y][x] == -1 ) 条件并且只使用 (moves < board[y] [x]) 在 else if 部分。

Answer 3

您正在进行深度优先搜索，这可能会找到某些方格的次优路径。

为了获得最佳路径，如果您的路径较短，您仍然应该从它访问，即使它已经被访问过。