คะแนนสูงสุดหลังจากพลิกเมทริกซ์ไบนารีสูงสุด K ครั้งใน C++

ปัญหา

ในปัญหานี้ เราได้รับอาร์เรย์ 2-D arr[] ที่ประกอบด้วยค่าบูลีน (0 และ 1) และจำนวนเต็ม K งานของเราคือสร้างโปรแกรมเพื่อหาคะแนนสูงสุดหลังจากพลิกเมทริกซ์ไบนารีสูงสุด K ครั้งใน C++

คำอธิบายปัญหา - ที่นี่ สำหรับอาร์เรย์ 2-D และ k การเคลื่อนไหว เราต้องหาตัวเลขที่สร้างจากสมาชิกของอาร์เรย์ ในแต่ละการเคลื่อนไหว เราจะเอาแถวหรือคอลัมน์หนึ่งและพลิกสมาชิกทั้งหมดของแถวหรือคอลัมน์นั้น การเลือกจะทำโดยคำนึงถึงว่าเราต้องเพิ่มตัวเลขที่สร้างขึ้นหลังจากพลิก K ครั้งในแถวของเมทริกซ์ และเราต้องคืนค่าผลรวมของตัวเลขทั้งหมดที่สร้างในแถว

ตัวอย่าง

มาดูตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

arr[][] = { 
    {1, 0, 0}, 
    {0, 1, 1}, 
    {1, 0, 1} 
} K = 2

เอาต์พุต

19

คำอธิบาย

เรามีการพลิก 2 ครั้ง

การพลิกครั้งแรก - เราจะพลิกสมาชิกแถวที่ 2 จะทำให้อาร์เรย์กลายเป็น

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

การพลิกครั้งที่สอง - เราจะพลิกสมาชิกคอลัมน์ที่ 2 จะทำให้อาร์เรย์กลายเป็น

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

ตัวเลขสุดท้ายที่สร้างในแต่ละแถวคือ 6, 6, 7

ผลรวมสูงสุด = 19

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

เพื่อแก้ปัญหานี้ เราต้องทำให้สมาชิกของคอลัมน์แรกเป็น 1 ก่อน เนื่องจาก 1 ที่คอลัมน์ที่ i จะมีส่วนร่วม 2^i ซึ่งจะเป็นตัวเลขที่ใหญ่ที่สุด (ถ้าพิจารณาบิตเซ็ตเพียงตัวเดียว) ดังนั้น คอลัมน์ซ้ายมือต้องมี 1 มากที่สุด (บิตเซ็ต) เพื่อทำให้ผลรวมสูงสุด จากนั้นเราจะไปที่สมาชิกอื่นๆ ของแต่ละแถว

เพื่อตรวจสอบว่าต้องพลิกแถวหรือคอลัมน์ เราต้องตรวจสอบค่าอื่นๆ ในคอลัมน์ นั่นคือสมาชิกแรกของทุกแถว หากจำนวน 0 มากกว่า 1 เราจะพลิกคอลัมน์ มิฉะนั้นพลิกแถว

เพื่อแก้ปัญหานี้ เราจะใช้โครงสร้างข้อมูล map

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

โปรแกรมแสดงการทำงานของคำตอบของเรา

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

const int row = 3; 
const int col = 3; 

int MaxSumAfterFlip(int mat[row][col], int K) { 
    map<int, int> flipValues; 
    int updateVal, MaxSum = 0; 
    for (int i = 0; i < row; ++i) { 
        if (mat[i][0] == 0) { 
            updateVal = 0; 
            for (int j = 1; j < col; ++j) 
                updateVal = updateVal + mat[i][j] * pow(2, col - j - 1); 
            flipValues[updateVal] = i; 
        } 
    } 
    map<int, int>::iterator it = flipValues.begin(); 
    while (K > 0 && it != flipValues.end()) { 
        int updateIndex = it->second; 
        for (int j = 0; j < col; ++j) 
            mat[updateIndex][j] = (mat[updateIndex][j] + 1) % 2; 
        it++; 
        K--; 
    } 
    MaxSum = 0; 
    int zeros, ones = 0; 
    for (int j = 0; j < col; ++j) { 
        zeros = ones = 0; 
        for (int i = 0; i < row; ++i) { 
            mat[i][j] == 0 ? zeros++ : ones++; 
        } 
        if (K > 0 && zeros > ones) { 
            MaxSum += zeros * pow(2, (col - j - 1)); 
            K--; 
        } 
        else 
            MaxSum += ones * pow(2, (col - j - 1)); 
    } 
    return MaxSum; 
} 

int main() { 
    int mat[row][col] = {{1, 0, 0 },{0, 1, 1},{1, 0, 1}}; 
    int K = 2; 
    cout<<"The Maximum score after flipping the matrix atmost K times is "<<MaxSumAfterFlip(mat, K); 
    return 0; 
}

เอาต์พุต

The Maximum score after flipping the matrix atmost K times is 19