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