0

T(x,y) を次のような X × Y グリッド上のツアーの数とします。

  1. ツアーは左上の四角から始まります
  2. ツアーは、1 マス上、下、左、または右の移動で構成されます。
  3. ツアーは各広場を 1 回だけ訪れます。
  4. ツアーは左下の四角で終了します。

たとえば、T(2,2) = 1、T(3,3) = 2、T(4,3) = 0、T(3,4) = 4 は簡単にわかります。 T(10,4) を計算します。

  • 私はこれに何時間も取り組んできました...グリッドの寸法を入力として取り、可能なツアーの数を返すプログラムが必要ですか? これを解決するにはどうすればよいですか？
4

2 に答える 2

1

あなたはバックトラックに慣れていないので、これを解決する方法がわかるかもしれません:

グリッド上のセルの状態 (訪問済み/未訪問) を表すデータ構造が必要です。

あなたのアルゴリズム:

step(posx, posy, steps_left)
    if it is not a valid position, or already visited
        return
    if it's the last step and you are at the target cell
        you've found a solution, increment counter
        return
    mark cell as visited             
    for each possible direction:
       step(posx_next, posy_next, steps_left-1)
    mark cell as not visited

と実行します

step(0, 0, sizex*sizey)

バックトラッキングの基本的な構成要素は、現在の状態の評価、マーキング、再帰ステップ、およびマーキング解除です。

これは、小さなボードでは問題なく機能します。本当の楽しみは、解けない木の枝を切らなければならない大きなボードから始まります (例: 訪問されていないセルの到達不可能な領域があります)。

于 2012-03-19T00:45:00.220 に答える
0

割り当てられた演習は良いものです。いくつかの概念を段階的に検討する必要があります。すべての概念を考え抜くことはできませんが、次の質問をすることでお役に立てるかもしれません。

ある時点で、プログラムは部分的に完了したツアーを表す必要があります。 つまり、まだすべての正方形を通過しておらず、左下のターゲットにまだ到達していないパスを表す必要がありますが、パスが後で拡張された場合、両方を実行する可能性があります。部分的に完了したツアーを表すとはどういう意味ですか?

質問に答えることができ、再帰の概念を理解することができれば、多少の作業で問題を解決できると思われますが、それほど大きな問題はありません。部分的に完了したツアーを代表することはあなたの障害なので、それに取り組むことをお勧めします。

更新: 以下の @KarolyHorvath のコメントを参照してください。動的に割り当てられたメモリ (または、同等に、std::vector や std::list などの STL コンテナー) の使用をまだ学習していない場合は、彼のヒントに従う必要があります。これはいずれにせよ良いヒントです。

于 2012-03-18T23:40:42.743 に答える