Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में अधिकतम K फ्लिप के बाद बाइनरी मैट्रिक्स का अधिकतम स्कोर


इस समस्या में, हमें एक 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
  1. C++ में बाइनरी मैट्रिक्स को शून्य मैट्रिक्स में बदलने के लिए ऑपरेशनों की गिनती करने का प्रोग्राम C++ में बाइनरी मैट्रिक्स को शून्य मैट्रिक्स में बदलने के लिए ऑपरेशनों की गिनती करने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। अब एक ऑपरेशन पर विचार करें जहां हम एक सेल लेते हैं और उसे और उसके सभी पड़ोसी सेल्स (ऊपर, नीचे, बाएं, दाएं) को फ्लिप करते हैं। हमें ऑपरेशनों की न्यूनतम संख्या ढूंढनी है जैसे कि मैट्रिक्स में केवल 0 हों। यदि कोई समाधान नहीं है, तो -1 वापस करें। तो, यदि इनप

  1. बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज

  1. - C++ का उपयोग करके मैट्रिक्स में अधिकतम योग वाला कॉलम खोजें

    मान लीजिए हमारे पास M x N आकार का एक मैट्रिक्स है। हमें वह कॉलम ढूंढना है जिसका योग अधिकतम है। इस प्रोग्राम में हम किसी ट्रिकी दृष्टिकोण का पालन नहीं करेंगे, बल्कि सरणी को कॉलम-वार पार करेंगे, प्रत्येक कॉलम का योग प्राप्त करेंगे, और यदि योग अधिकतम है, तो उस योग और कॉलम इंडेक्स को प्रिंट करेंगे। उदा