複数の NxN グリッドがあり、いくつかのコマンドに基づいてそれらの特定の位置を操作したいとします。C++ でこれを行う最も効率的な方法にはどのようなものがありますか?
わかりやすくするために、次のファイルがあると考えてください。
world.txt:
2 O O
O O O
X O X
-----
X O X
O O O
1 O O
これは 2 つの 3x3 グリッドを表します。また、わかりやすくするために (ただし、実際には問題ではありません)、私のタスクは、1 から 2 に到達するために取られた場所を出力するアルゴリズムを実装することでした (どのようなルートを使用しても)。この種のデータを C++ に格納し、いくつかのルールに基づいて個々の場所に作用する最も効率的な方法は何ですか? この形式のデータを扱うのに適しているデータ構造は何ですか?
スペース効率、またはアクセス速度 (またはその他のほとんどすべて) については、2D 配列に勝るものはありません。より複雑な構造がもたらすものは、スペースや速度をいくらか犠牲にして、問題をより直感的に表現することです。
例として、グリッドをグラフとして表し、各ノード (頂点) がその隣接ノードへのポインター (エッジ) のリストを持っているとします。この表現では、表現が明らかにグラフであるため、問題をグラフの問題としてキャストし、より簡単に概念化された方法で処理 (ダイクストラ最短経路検索など) を行うことができます。2D 配列のままにしておくと、たとえば、隣接規則を明示的にエンコードする必要があるため、多少の複雑さを犠牲にしてストレージ効率が得られます (コーナーのノードには 2 つの隣接ノード、エッジのノードは 3 など)。プログラム ロジック内のグラフ トラバーサル ルール。
このような単純なものについては、配列に固執します。しかし、それは完全に個人的な好みです。より説明的なものを求めている場合、グラフ表現の方が優れていることがわかります。（さらに、任意の構成に対してより一般化されます。）