2

私は最近C++、特にSTLについて読んでいて、KnightsTourの問題をもう一度やり直すことにしました。私はこれを実装するための最良の方法を考えています、そして私はいくつかの助けを探しています。

楽しみと練習のために、「ナイト」クラスから継承できる「ピース」基本クラスから始めようと思いました。後で他のピースを追加してみることができるように、これを実行したいと思います（ほとんどのピースがボード全体をウォークオーバーして問題を完了することはできませんが）。

したがって、「ピースクラス」には、ボード上のピースの座標と、その特定のステップで行った移動の数を格納するための、ある種のコンテナが必要になります。

これを最も効率的に行うには、x、y、およびmovesを含む64（8 * 8）の場所を持つリンクリストが必要だと思います。

STLコンテナを見ると、複数のタイプを保持するマップ以外は見つかりません。

1つのコンテナに移動数の座標ペアとintを格納するにはどうすればよいですか？ベクトル、リスト、またはマップを使用するよりも効率的な方法はありますか？カスタムコンテナが必要ですか？

ありがとう！

4

3 に答える 3

2

使用できます

struct CellInfo
{
    int x, y, move_count;
}

そしてstd::vector、常にアクセスできるように保管してください。

于 2012-10-24T18:01:33.240 に答える
0

STLとカプセル化とは別に、非常に効率的な方法は配列を使用することです。

pair<int, int> piece_pos[N];
int piece_move[N];

これにより、メモリリークのオーバーヘッドが回避され、動的割り当てよりも高速になります。

STLを使用したい場合は、次のようにします。

vector<pair<int, int> > piece_pos(N);
vector<int> piece(N);
于 2012-10-24T18:06:23.133 に答える
0

C ++ STLには、静的配列も含まれるようになりました。特定のx、y座標が移動された回数を保存する場合は、次のような配列の配列を作成できます。

using container_type = std::array<std::array<int, 8>, 8>;

// ...

container_type c;
int moves = c[x][y]; // constant-time access.

x、yに基づいて上に移動する必要がなく、データを効率的に保存したい場合は、サイズ8x8=64のフラット配列を使用します。

コンパイラが古くなっている場合は、代わりにstd::vectorの使用を検討してください。

于 2012-10-24T18:41:19.037 に答える