c# - 正方行列上の最適図形配置

Question

次の問題を解決しようとしていますが、方法がわかりません。

一連の図形 (線、四角形、「プラス」など) があり、最初は行列に配置されているため、一部が重なっています。数字が重ならないように、最小の手数を探しています。フィギュアは斜めには動かず、縦と横だけ動きます。

ありがとう

Answer 1

幅優先検索ソリューションの概要は次のとおりです。

• それぞれが行列内のすべての図形の一意の位置を表し、エッジが単一の図形の正当な動き (図形が行列の外に移動しない上下左右) を表す頂点で構成される(暗黙的な) グラフを想定します。 ）。
• 初期の Figure 構成を表すノードを未訪問としてマークされた BFS キューに追加することにより、このグラフで幅優先検索を実行します。
• キュー内の未訪問のノードごとに、オーバーラップがないかどうかを確認し、完了している場合は、訪問済みとしてマークし、隣接ノード (その構成からのすべての図のすべての可能なワンステップ移動) を追加します。 BFS キューの終わり。HashSet を使用して、アクセスしたノード (フィギュアの場所の一意の構成) を保存できます。これは、同一の構成に異なる移動シーケンスで到達できるためです。
• BFS キューが空になった場合、考えられるすべての図の構成を確認したため、解決策はありません。