इस समस्या में, हमें बूलियन मानों (यानी 0 और 1 के) और एक पूर्णांक K से मिलकर 2-डी सरणी arr[] दिया जाता है। हमारा काम बाइनरी मैट्रिक्स को लगभग K बार फ़्लिप करने के बाद अधिकतम स्कोर खोजने के लिए एक प्रोग्राम बनाना है। सी++.
समस्या का विवरण - यहां, 2-डी सरणी और के चाल के लिए, हमें उस संख्या को खोजने की आवश्यकता है जो सरणी के तत्वों द्वारा बनाई गई है। प्रत्येक चाल में, हम एक पंक्ति या स्तंभ लेंगे और पंक्ति या स्तंभ के सभी तत्वों को फ्लिप करेंगे। चुनाव इस बात को ध्यान में रखने के लिए किया जाएगा कि मैट्रिक्स की एक पंक्ति में K फ़्लिप किए जाने के बाद हमें बनाई गई संख्या को अधिकतम करने की आवश्यकता है। और हमें पंक्ति में बनाए गए सभी नंबरों का योग वापस करना होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[][] = {
{1, 0, 0},
{0, 1, 1},
{1, 0, 1}
}
K = 2 आउटपुट
19
स्पष्टीकरण
हमारे पास दो फ़्लिप हैं,
पहला फ्लिप - हम दूसरी-पंक्ति के तत्वों को फ्लिप करेंगे। यह सरणी बना देगा,
{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}} दूसरा फ्लिप - हम दूसरे कॉलम तत्वों को फ्लिप करेंगे। यह सरणी बना देगा,
{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}} प्रत्येक पंक्ति में बनाई गई अंतिम संख्या 6, 6, 7 होती है।
Maximum sum = 19.
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें पहले कॉलम 1 का तत्व बनाना होगा। जैसा कि ith कॉलम में 1 2i में योगदान देगा जो कि सबसे बड़ी संभव संख्या होगी (यदि एक सेट बिट माना जाता है)। इसलिए, योग को अधिकतम बनाने के लिए सबसे बाएं कॉलम में अधिकतम संख्या 1 (सेट बिट्स) होनी चाहिए। फिर हम प्रत्येक पंक्ति के अन्य तत्वों के लिए जाएंगे।
यह जाँचने के लिए कि क्या मुझे पंक्ति या स्तंभ को फ़्लिप करने की आवश्यकता है। हमें कॉलम में अन्य मानों की जांच करने की आवश्यकता है। यानी पंक्तियों के सभी पहले तत्व। यदि 0 की संख्या 1 से अधिक है। हम कॉलम को फ़्लिप करेंगे अन्यथा पंक्ति को फ़्लिप करेंगे।
समस्या को हल करने के लिए, हम मानचित्र डेटा संरचना का उपयोग करेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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