Tiền truyện ma trận lật trong C ++

Giả sử chúng ta có một ma trận nhị phân. Chúng ta phải tìm số 1s tối đa mà chúng ta có thể nhận được nếu chúng ta lật một hàng và sau đó lật một cột.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 8

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

• n:=kích thước của các hàng trong ma trận

• m:=kích thước của các cột trong ma trận

• ret:=0

• Xác định một hàng mảng có kích thước n

• Xác định col mảng có kích thước n

• tổng:=0

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • row [i]:=row [i] + ma trận [i, j]

    • col [j]:=col [j] + matrix [i, j]

    • tổng:=tổng + ma trận [i, j]

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • cand:=total - row [i] - col [j] + ((m - row [i]) + (n - col [j]))

    • nếu ma trận [i, j] khác 0 thì -

      • cand:=cand + 2

    • Nếu không

      • cand:=cand - 2

    • ret:=tối đa là ret và cand

• 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 solve(vector<vector<int>> &matrix) {
      int n = matrix.size();
      int m = matrix[0].size();
      int ret = 0;
      vector<int> row(n);
      vector<int> col(m);
      int total = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            row[i] += matrix[i][j];
            col[j] += matrix[i][j];
            total += matrix[i][j];
         }
      }
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            int cand = total - row[i] - col[j] + (m - row[i]) + (n -
            col[j]);
            if (matrix[i][j]) {
               cand += 2;
            }else {
               cand -= 2;
            }
            ret = max(ret, cand);
         }
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{1,0,1},{0,1,0},{1,0,0}};
   cout << (ob.solve(v));
}

Đầu vào

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

Đầu ra

8