Ma trận lật ngược tiền đề trong C++

Cho ma trận nhị phân. Cần tìm số lượng bit 1 tối đa có thể đạt được nếu lật một hàng và một cột (lật nghĩa là đổi 0↔1).

Ví dụ ma trận 3x3:
1 0 1
0 1 0
1 0 0
Kết quả: 8.

Giải thuật:

• Tính tổng số 1 của mỗi hàng (row[i]), mỗi cột (col[j]) và tổng cả ma trận (total).
• Với mỗi ô (i,j), tính số 1 sau khi lật hàng i và cột j: cand = total - row[i] - col[j] + (m - row[i]) + (n - col[j]) Nếu matrix[i][j] == 1 thì cand += 2, ngược lại cand -= 2.
• Lấy max của tất cả cand.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int ret = 0;
        vector<int> row(n), 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;
    }
};

int 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