* n バイナリ行列を考えてみましょう。この行列の各セルには、最大で 4 つの近傍 (存在する場合) があります。この行列の 2 つのセルが隣接しており、それらの値が等しくない場合、互換性がないと呼びます。互換性のないペアごとに $b を支払います。$a を支払うことでセルの値を変更することもできます。
問題は、このマトリックスの最小コストを見つけることです。
私はすでにバックトラッキングを使用し、 のアルゴリズムを見つけましたO(2 ^ (n * n))
。誰かがより効率的なアルゴリズムを見つけるのを手伝ってくれますか?