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

C++ में फ़्लिप्ड मैट्रिक्स प्रीक्वल


मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। हमें अधिकतम 1s की संख्या ज्ञात करनी है जो हम प्राप्त कर सकते हैं यदि हम एक पंक्ति और फिर एक स्तंभ को फ्लिप करते हैं।

उदाहरण के लिए, यदि इनपुट है:

101
010
100
तो आउटपुट 8 होगा।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • n := मैट्रिक्स में पंक्तियों का आकार
  • m := मैट्रिक्स में स्तंभों का आकार
  • ret := 0
  • आकार n की एक सरणी row परिभाषित करें
  • आकार m की एक सरणी col परिभाषित करें
  • total := 0
  • i := 0 से n-1 तक लूप चलाएं:
    • j := 0 से m-1 तक लूप चलाएं:
      • row[i] := row[i] + matrix[i][j]
      • col[j] := col[j] + matrix[i][j]
      • total := total + matrix[i][j]
  • i := 0 से n-1 तक लूप चलाएं:
    • j := 0 से m-1 तक लूप चलाएं:
      • cand := total - row[i] - col[j] + ((m - row[i]) + (n - col[j]))
      • यदि matrix[i][j] शून्येतर है:
        • cand := cand + 2
      • अन्यथा:
        • cand := cand - 2
      • ret := ret और cand का अधिकतम
  • ret लौटाएं।

C++ कार्यान्वयन

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

class Solution {
public:
    int solve(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        int ret = 0;
        vector<int> row(n);
        vector<int> col(m);
        int total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                row[i] += matrix[i][j];
                col[j] += matrix[i][j];
                total += matrix[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cand = total - row[i] - col[j] + (m - row[i]) + (n - col[j]);
                if (matrix[i][j]) {
                    cand += 2;
                } else {
                    cand -= 2;
                }
                ret = max(ret, cand);
            }
        }
        return ret;
    }
};

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

इनपुट

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

आउटपुट

8
  1. C++ में मैट्रिक्स की पंक्ति-वार बनाम स्तंभ-वार ट्रैवर्सल C++ में मैट्रिक्स की पंक्ति-वार बनाम स्तंभ-वार ट्रैवर्सल

    एक मैट्रिक्स को दो तरीकों से ट्रैवर्स किया जा सकता है। पंक्ति-वार ट्रैवर्सल प्रत्येक पंक्ति को एक-एक करके पहले पंक्ति से शुरू करके अंतिम पंक्ति तक देखता है। पंक्ति में तत्व इंडेक्स 0 से अंतिम इंडेक्स तक लौटाए जाते हैं। स्तंभ-वार ट्रैवर्सल में, तत्वों को पहले स्तंभ से अंतिम स्तंभ तक क्रम में ट्रैवर्स

  1. C++ में स्पाइरल मैट्रिक्स III (Spiral Matrix III) C++ में स्पाइरल मैट्रिक्स III (Spiral Matrix III)

    मान लीजिए हमारे पास R पंक्तियों और C स्तंभों वाला एक 2-आयामी ग्रिड है, हम (r0, c0) से शुरू करते हैं और पूर्व की ओर मुख किए होते हैं। यहां, ग्रिड का उत्तर-पश्चिम कोना पहली पंक्ति और स्तंभ पर है, और दक्षिण-पूर्व कोना अंतिम पंक्ति और स्तंभ पर है। हम इस ग्रिड में हर स्थिति को देखने के लिए दक्षिणावर्त स

  1. - C++ में बूलियन मैट्रिक्स प्रश्न

    यहां हम एक रोचक बूलियन मैट्रिक्स समस्या देखेंगे। एक बूलियन मैट्रिक्स दिया गया है जिसमें 0 और 1 हैं। हमारा लक्ष्य यह ढूंढना है कि 1 कहां मार्क किया गया है। यदि 1 स्थिति mat[i,j] पर मार्क किया गया है, तो हम पंक्ति i और स्तंभ j के सभी एंट्रीज को 1 बना देंगे। एक उदाहरण देखते हैं। यदि मैट्रिक्स नीचे जैसा