java - 最小の「XOR」演算でバイナリマトリックスを再作成する

原文 java c++ algorithm binary xor

これは、高校時代のコーディングコンテストの質問でした。基本的なアイデアは、長方形のXOR演算のみで白黒の絵を再現することでした。

問題

再現しようとしているこの絵があるとしましょう(バイナリマトリックスとして表され、0は黒、1は白です)。

1 0 0
1 1 1
1 0 1


絵画を再現する1つの方法は、次の操作です。

(0, 0) (2, 2)
(1, 0) (2, 0)
(1, 2) (1, 2)


操作は(xStart, yStart) (xEnd, yEnd)の形式です

したがって、すべて黒のキャンバスから開始すると、上記の操作は次のようになります。

beginning:

    0 0 0
    0 0 0
    0 0 0

after (0, 0) (2, 2) :

    1 1 1
    1 1 1
    1 1 1

after (1, 0) (2, 0) :

    1 0 0
    1 1 1
    1 1 1

after (1, 2) (1, 2) :

    1 0 0
    1 1 1
    1 0 1




割り当てに関する技術:


勝者は操作が最も少ない。
1つの操作は(xStart, yStart) (xEnd, yEnd)の形式にする必要があります。
時間やスペースの制約はありません。
この割り当てでは、再現しようとしている絵のサイズは200x200で、2000回のランダムXOR演算で生成されました。




私自身のアイデア

これを行うにはいくつかの方法があります。悪いものから最も良いものの順にここにリストします。

すべてのピクセルのXOR:

再現しようとしている絵に1が存在する空白のキャンバスに1を書き込むだけで、絵を再現できます。このソリューションは、最も単純で最も明白です。必要な操作の数は、基本的には絵の白いピクセルの量です。

水平方向に隣接するすべての白のXOR:

これは最初のソリューションからの大幅な改善ですが、それでも非常に単純で明白です。この方法では、水平方向に隣接するすべての白を単純にXORします。このように、例えば操作

(0, 0) (0, 0)
(1, 0) (1, 0)
(2, 0) (2, 0)


(0, 0) (2, 0)に減少します。

XOR長方形:

これは、前の方法の明確なフォローアップだと思います。これは、高さ1のXORing長方形として見ることができます。これで、長方形に2番目の次元を追加するだけで、結果がさらに向上します。白が最も多い長方形を取得して、XOR可能領域を決定しました。改善はまだ良好です。

XORの最大の違い:

これは、上記の方法からのわずかな変更であり、少し力づくです。この方法では、絵との違いが最も大きい長方形を見つけ、XORします。たとえば、絵画がある場合

1 0 1
0 1 1
0 1 0


真っ黒なキャンバスの場合、最大の違いは長方形(0, 0) (2, 1)で、2の違いがあります。私は、上記の状況では4である、絵のすべての同じでない色を取得することで違いを計算します。次に、同じ色の量を上記の状況では2から差し引きます。つまり、different_colors - same_colors = differenceです。

上の絵と空白のキャンバスには、同じ違いを生み出す長方形がたくさんあります。もう1つは(1, 0) (2, 2)です。

この方法は、以前の大きな絵画の方法からの改善が最小でしたが、それでも改善されました。興味深いことに、この方法は、以前の小さな絵を使った方法よりも悪い解決策を思いついたことがあります(ただし、どれほど小さいか思い出せません)。



上記の方法で使用したコードはすべて失われてから長い間使用されていません。あなたは息をのむような解決策を思いつくことができますか?宇宙から魔法のようなアプローチはありますか?この質問(投稿)はかなり興味深いものであり、誰かが何かを思い付くことができるかどうかを確認したいと思います。



タグについて

これはJavaとC++の両方でタグ付けしました。この質問が特にこれらの言語に関係しているからではなく、これらの言語で記述されたコードや、同様の構文を持つ言語を簡単に理解できるためです。
答え
このタスクを完了するには、ゼロのみを含む最大サイズのサブマトリックスの座標を見つける必要があると思います。

私はそのアルゴリズムを説明できますが、次のリンクが最も良い説明だと思います:

Maximum size sum-matrix with all 1s in binary matrix

ここでの解決策はすべて1の場合で、すべて0の場合は変更できます。

次に、最大値から座標を見つけて操作するだけです。

より良い方法が思いつかれば更新します。
関連記事

java - 特定の解像度の画像を選択するとアプリケーションがクラッシュする

java - mockmvc standalonesetupフリーマーカーのviewresolverを注入する方法?

java - パスの.relativize()ドキュメントのバグか、ここで露骨に何か間違ったことをしていますか?

java - クラス階層とセットアップ

java - Usage TrackerのJavaプロパティファイルでユーザー名を解決する

java - ボタン付きのビューページャーでフラグメント間をスワイプできません

java - 同じアクティビティ内のAdMobとWebViewが機能しない(Androidアプリ)

java - Android Gstreamer SDKでANativeWindow_lockがエラー-22を返す

java - Lucene Library 4.1.0でプラス記号をエスケープする方法

java - 特定のメソッドからのメソッドへの呼び出しの検出または防止