C++でバイナリ行列を最大K回反転した後の最大スコア

この問題では、ブール値（つまり、0と1）と整数Kで構成される2次元配列arr []が与えられます。私たちのタスクは、バイナリ行列を最大でK回反転した後、最大スコアを見つけるプログラムを作成することです。 C++。

問題の説明 −ここで、2次元配列の場合、kが移動するため、配列の要素によって作成される数を見つける必要があります。各移動で、行または列を取得し、行または列のすべての要素を反転します。この選択は、行列の行でK回の反転が行われた後に作成される数を最大化する必要があることを念頭に置いて行われます。そして、行に作成されたすべての数値の合計を返す必要があります。

問題を理解するために例を見てみましょう

入力

arr[][] = {
   {1, 0, 0},
   {0, 1, 1},
   {1, 0, 1}
}
K = 2

出力

19

説明

2つのフリップがあります

最初のフリップ-2行目の要素をフリップします。これにより、アレイが作成されます

{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}}

2番目のフリップ-2番目の列要素をフリップします。これにより、アレイが作成されます

{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}}

各行で作成される最終的な番号は6、6、7です。

Maximum sum = 19.

ソリューションアプローチ

この問題を解決するには、最初の列の要素を最初にする必要があります。 i番目の列の1は、可能な最大数になる2iに寄与します（1セットビットを考慮した場合）。したがって、合計を最大にするには、左端の列の最大数が1（セットビット）である必要があります。次に、各行の他の要素に進みます。

行または列を反転する必要があるかどうかを確認します。列の他の値を確認する必要があります。つまり、行のすべての最初の要素。 0の数が1よりも大きい場合。列を反転します。それ以外の場合は行を反転します。

この問題を解決するために、マップデータ構造を使用します。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;
const int row = 3;
const int col = 3;
int MaxSumAfterFlip(int mat[row][col], int K) {
   map<int, int> flipValues;
   int updateVal, MaxSum = 0;
   for (int i = 0; i < row; ++i) {
      if (mat[i][0] == 0) {
         updateVal = 0;
         for (int j = 1; j < col; ++j)
            updateVal = updateVal + mat[i][j] * pow(2, col - j- 1);
         flipValues[updateVal] = i;
      }
   }
   map<int, int>::iterator it = flipValues.begin();
   while (K > 0 && it != flipValues.end()) {
      int updateIndex = it->second ;
      for (int j = 0; j < col; ++j)
         mat[updateIndex][j] = (mat[updateIndex][j] + 1) % 2;
      it++;
      K--;
   }
   MaxSum = 0;
   int zeros, ones = 0;
   for (int j = 0; j < col; ++j) {
      zeros = ones = 0;
      for (int i = 0; i < row; ++i) {
         mat[i][j] == 0 ? zeros++ : ones++;
      }
      if (K > 0 && zeros > ones) {
         MaxSum += zeros * pow(2, (col - j - 1));
         K--;
      }
      else
         MaxSum += ones * pow(2, (col - j - 1));
   }
   return MaxSum;
}
int main() {
   int mat[row][col] = {{1, 0, 0 },{0, 1, 1},{1, 0, 1}};
   int K = 2;
   cout<<"The Maximum score after flipping the matrix atmost K times is "<<MaxSumAfterFlip(mat, K);
   return 0;
}

出力

The Maximum score after flipping the matrix atmost K times is 19