C++でマトリックスを反転した後のスコア

各値が0または1である2次元行列Aがあるとします。ここでの移動は、任意の行または列を選択し、その行または列の各値を切り替えることで構成されます。つまり、すべて0を1に、すべて1を0に変更します。これで、任意の数の移動を行った後、このマトリックスのすべての行が2進数として解釈され、マトリックスのスコアはこれらの数値の合計になります。したがって、私たちのタスクは、可能な限り最高のスコアを見つけることです。入力が-

トグル後の出力は39になり、行列は-

したがって、数値は15 + 9 + 15 =39

これを解決するには、次の手順に従います-

• n：=行数およびm：=列数

• ret：=n x（2 ^（m – 1））

• 1からm–1の範囲のjの場合

  • cnt：=0

  • 0からn–1の範囲のiの場合

    • cnt：=cnt + A [i、j] =A [i、0]

  • temp：=2 ^（m – j – 1）*cntおよびn–cntの最大値

  • ret：=ret + temp

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int matrixScore(vector<vector<int>>& A) {
      int n = A.size();
      int m = A[0].size();
      int ret = (1 << (m - 1)) * n;
      for(int j = 1; j < m; j++){
         int cnt = 0;
         for(int i = 0; i < n; i++){
            cnt += (A[i][j] == A[i][0]);
         }
         int temp = ((1 << (m - (j + 1))) * max(cnt, n - cnt));
         ret += temp;
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
   Solution ob;
   cout << (ob.matrixScore(v));
}

入力

[[0,0,1,1],[1,0,1,0],[1,1,0,0]]

出力

39