1

私はこの機能を持っていますが、どうやらプログラムがクラッシュする原因になっているようです:

long long todos(long long x,long long i) {
  x ^= (1 << i);
  long long aux = i - 1;
  if(aux >= 0) x ^= (1 << aux);
  aux = i - 4;
  if(aux >= 0) x ^= (1 << aux);
  aux = i + 1;
  if(aux < 16) x ^= (1 << aux);
  aux = i + 4;
  if(aux < 16) x ^= (1 << aux);
  return x;
}

私が理解していないのは、すべての^= (forを変更する&= ~(と完全に正常に動作する理由です (ただし、得られる出力は異なります)。この動作の論理的な説明はありますか?

コード全体が必要な場合: http://ideone.com/Z7qoof

4

2 に答える 2

1

dp()関数が非常に深く再帰しているように見えます。を呼び出すと、 をdp(3)使用して 65536 個の可能なすべてのビットボードを順番に評価できることを考慮して^ください。に順番に入力していることに注意してください。の前にビットボードに数値的にのみ依存している場合、あまり深く再帰することはありません。&~dp(k)kmatmain()k

EDIT : この問題の修正に関しては、動的計画法を有向非巡回グラフの最短経路と考えることができます。問題は、ここに非循環グラフがないことです。ここで最短パスを見つけるために深さ優先検索を行っていますが、うまくいきません。幅優先探索やダイクストラのアルゴリズムなどに置き換えてみてください。

于 2012-11-27T12:57:37.183 に答える
0

私の推測では、次の行がクラッシュします。

cout << mat[bs.to_ulong()] << endl;

bs が 1<<16 の予約済みスペースよりも大きいため

ps なぜすべてに long long データ型を使用するのですか? long long は 64 ビットです。あなたが行うほとんどのことは、おそらく短いintで行うことができます

于 2012-11-27T12:56:44.700 に答える