C++-এ ফ্লিপড ম্যাট্রিক্স প্রিক্যুইল: সারি ও কলাম ফ্লিপ করে ১ সংখ্যা বাড়ানো

একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে। একটি সারি এবং একটি কলাম ফ্লিপ করে (০↔১) সর্বোচ্চ কতটি ১ পাওয়া যায় তা বের করুন।

উদাহরণ

ইনপুট: {{1,0,1}, {0,1,0}, {1,0,0}}

আউটপুট: 8

অ্যালগরিদম

1. প্রতিটি সারি ও কলামে ১-এর সংখ্যা গণনা করুন (row[i], col[j])।
2. মোট ১-এর সংখ্যা = total।
3. প্রতিটি সেল (i,j) ফ্লিপ করলে নতুন ১-এর সংখ্যা: cand = total - row[i] - col[j] + (m - row[i]) + (n - col[j])
4. যদি matrix[i][j] == 1 হয়, cand += 2; অন্যথায় cand -= 2।
5. সর্বোচ্চ cand বের করুন।

C++ বাস্তবায়ন

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

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

সময় জটিলতা

O(n × m) - ম্যাট্রিক্স ট্রাভার্সালের জন্য।