アルゴリズム：2Dマトリックスの再配置（要素の反転）

Question

以下の（効率的に）解決するアルゴリズムについては疑問に思っています。数字の[1..9]の行列で、 1）から底部（9）まで、垂直方向または水平方向に別の番号で反転させるだけである。

例入力マトリックス：

1 8 2 6 1 6 
9 2 5 1 6 2 
3 6 9 2 9 8 
5 1 7 4 2 8 
4 2 7 6 9 5 

所望の出力マトリックス： 'フリッピング' に関する

1 1 1 1 2 2 
2 2 2 2 3 4 
4 5 5 5 6 6 
6 6 6 7 7 8 
8 8 9 9 9 9 

明確化：例えば入力行列を取ります。左上隅に「1」があります。その1は横に8の横にフリップするか（最初の行は今度は8 1 2 6 1 6になります）、またはその下の9で垂直にフリップすることができます（最初の列は現在9 1 3 5 4になります）。それは斜めに2で反転することはできません。

この問題の解決方法（言語は問題ありません）はありますか？

Answer 1

斜めにフリップできない部分は赤いニシンです。 （要素をその要素の横に並べ、その下に配置するだけで要素を反転させます）。したがって、任意の要素は、繰り返しフリップすることで、マトリックス内の他の要素と交換できます。この推論の行を続けると、希望の最終状態が、要素を昇順で含み、左から右へ、上から下へ（最終状態で）増加する行列であることがわかります。

この最終結果をすばやく生成するには、最初の行列を2次元配列からフラットリストに変更します。ソート。次に、2次元配列に戻します。

あなたが最終的な結果を生成することができ、法的移動（このようなシーケンスがユニークないであることに注意！）の配列を知る必要がある場合は、次のような単純なアルゴリズムはそれを行います。

1. スタートにより、左上隅にある要素を配置する。これが現在の位置です。
2. 残りの行列の最小要素を求めます。
3. 現在の位置の列に到達するまでこの要素を左に、次に現在の位置の行に到達するまで上に移動します。
4. 現在の位置を適切に配置した位置にマークを付けます。
5. 行全体が配置されている場合は、現在の位置を1つ右に移動するか、次の行の先頭に移動して次の位置に移動します。
6. マトリックス全体が配置されるまで繰り返す。

最適に効率的ですか？ありそうもない。シンプルで効果的ですか？絶対に。

Answer 2

素敵なパズル！とにかくソートアルゴリズムのバージョンを変更することができます。私は実装にはあまり良いことではないが、私はあなたに後でそれを与えることを試みることができる。これを解決する別の方法はA *アルゴリズムです。人工知能で使用される経路探索アルゴリズムですが、これと同様の問題にも適用されています。