我正在尝试更好地理解递归,所以我决定编写一个程序来确定 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