Score After Flipping Matrix ใน C++

คำอธิบายปัญหา

เมทริกซ์ A ค่า 0/1 สามารถพลิกแถวหรือคอลัมน์ได้ (0↔1) หลังจากพลิกแล้ว แต่ละแถวอ่านเป็น binary number คะแนน = ผลรวม ต้องการคะแนนสูงสุด

ตัวอย่าง: [[0,0,1,1],[1,0,1,0],[1,1,0,0]] → 39

วิธีแก้ปัญหา (Greedy)

1. คอลัมน์แรก: พลิกแถวที่มี 0 ให้กลายเป็น 1 (คอลัมน์แรกมีน้ำหนักสูงสุด 2^(m-1))
2. สำหรับคอลัมน์ j > 0: นับจำนวน 1 หลังจากพิจารณาการพลิกแถวแล้ว
3. เลือกพลิกคอลัมน์หรือไม่ เพื่อให้ 1 มากที่สุด: max(cnt, n-cnt) * 2^(m-j-1)

ตัวอย่างโค้ด C++

#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();
        
        // คอลัมน์แรก: ทำให้เป็น 1 ทั้งหมดโดยพลิกแถว
        int score = n * (1 << (m - 1));
        
        for(int j = 1; j < m; j++) {
            int cnt = 0;
            for(int i = 0; i < n; i++) {
                // ค่าจริงหลังพลิกแถวตามคอลัมน์แรก
                int val = A[i][j] == A[i][0] ? 1 : 0;
                cnt += val;
            }
            int maxOnes = max(cnt, n - cnt);
            score += maxOnes * (1 << (m - j - 1));
        }
        return score;
    }
};

int main() {
    vector<vector<int>> v = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
    Solution ob;
    cout << ob.matrixScore(v);
    return 0;
}

อินพุต

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

เอาต์พุต

39