2

私は再帰をよりよく理解しようとしている最中なので、再帰を使用して、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

最初の2行は正しいですが、最後の行（最後の行の最後の列を除く）は間違っています。そのはず：

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
4

3 に答える 3

3 
else if (board[y][x] != -1) {
    // already visited, check if path is shorter
    if (moves &lt; 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;
  }
}

期待どおりに動作します。

于 2012-04-26T15:33:09.633 に答える
1

深さ優先探索を実行しているため、一部の正方形への最適ではないパスが見つかる可能性があります。

最適なパスを取得するには、パスが短い場合は、すでにアクセスしている場合でも、そこからアクセスする必要があります。

于 2012-04-26T15:35:19.253 に答える
1

これはうまくいくでしょう。

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);
  }
}

さらに、ボードの各要素を-1ではなく（2 * n-2）で初期化すると、（board [y] [x] == -1）条件を削除して、（moves <board [y] [x]）elseif部分。

于 2012-04-26T15:56:55.427 に答える