Điểm sau khi lật ma trận trong C ++

Giả sử chúng ta có một ma trận hai chiều A trong đó mỗi giá trị là 0 hoặc 1. Ở đây, một bước di chuyển bao gồm việc chọn bất kỳ hàng hoặc cột nào và chuyển đổi từng giá trị trong hàng hoặc cột đó:thay đổi tất cả các số 0 thành 1 và tất cả các 1 thành 0. Bây giờ sau khi thực hiện một số lần di chuyển, mọi hàng của ma trận này được hiểu là một số nhị phân và điểm của ma trận là tổng của các số này. Vì vậy nhiệm vụ của chúng ta là tìm ra điểm cao nhất có thể. Nếu đầu vào giống như -

0	0	1	1
1	0	1	0
1	1	0	0

Đầu ra sẽ là 39 vì sau khi chuyển đổi, ma trận sẽ là -

1	1	1	1
1	0	0	1
1	1	1	1

Vậy các số là 15 + 9 + 15 =39

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=số hàng và m:=số cột
ret:=n x (2 ^ (m - 1))
cho j trong phạm vi từ 1 đến m - 1
- cnt:=0
- cho tôi trong phạm vi từ 0 đến n - 1
  - cnt:=cnt + A [i, j] =A [i, 0]
- temp:=2 ^ (m - j - 1) * tối đa là cnt và n - cnt
- ret:=ret + temp
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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