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）を計算します。

私はこれに何時間も取り組んできました...グリッドの寸法を入力として受け取り、可能なツアーの数を返すプログラムが必要ですか？

私はこれに何時間も取り組んできました...グリッドの寸法を入力として受け取り、可能なツアーの数を返すプログラムが必要ですか？

私は問題を解決するためにこのコードを書きました...私はすべての方向をチェックする方法を理解できないようです。

#include <iostream>

int grid[3][3];
int c = 0;

int main(){    
    solve (0, 0, 9);
}

int solve (int posx, int posy, steps_left){
    if (grid[posx][posy] = 1){
        return 0;
    }
    if (steps_left = 1 && posx = 0 && posy = 2){
        c = c+1;
        return 0;
    }
    grid[posx][posy] = 1;
    // for all possible directions
    {
        solve (posx_next, posy_next, steps_left-1)
    }
    grid[posx][posy] = 0;
}

@KarolyHorvathによるアルゴリズムグリッド上のセルの状態（訪問済み/未訪問）を表すために、いくつかのデータ構造が必要です。

あなたのアルゴリズム：

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）で実行します

4

2 に答える 2

0

アルゴリズムが与えられているので、難しいことではありません。この問題を解決するには、おそらく何らかの動的データ構造が必要になるでしょう (T(10,4) の正確なケースだけに関心がある場合を除く)。残りの場合、左は x インデックスで -1、右は +1、下は y 次元で -1、上は +1 です。訪問していない境界チェックと検証を追加すると、作業は完了です。

しかし、そのような明白なアルゴリズムにはどれくらいの時間がかかるのだろうか. 各セルには 4 つの決定があります。T(10,4) の 40 個のセルの場合、4^40 の決定です。これは実現不可能です。すでにアクセスしたセルを削除したり、境界チェックを行ったりすると、多くの分岐が削除されますが、それでも... 競争の目的は、より優れたアルゴリズムを見つけることです。

于 2012-03-19T18:55:57.597 に答える
0

デバッガーを選択して、小さなボード (2x2、3x3) で何が起こっているかを確認する必要があります。

明らかな問題の 1 つは=、比較ではなく代入であることです。と比較してください==。

さらに問題があります。それらを見つけます。

于 2012-03-19T23:15:54.063 に答える