C++ में मैट्रिक्स में अधिकतम संख्या में 1s

मान लीजिए हमारे पास w x h आयामों का एक मैट्रिक्स M है, जैसे कि प्रत्येक सेल का मान 0 या 1 है, और M का आकार l x l का कोई भी वर्ग सब-मैट्रिक्स में अधिकतम maxOnes संख्या में 1s हैं। हमें मैट्रिक्स M में हो सकने वाले 1s की अधिकतम संभव संख्या ज्ञात करनी है।

तो, यदि इनपुट w = 3, h = 3, l = 2, maxOnes = 1 है, तो आउटपुट 4 होगा क्योंकि 3*3 मैट्रिक्स में, कोई 2*2 सब-मैट्रिक्स 1 से अधिक 1 नहीं रख सकता। 4 1s वाला सर्वोत्तम समाधान है:

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• ret := 0

• आकार n x n का एक 2D ऐरे sq बनाएं

• i := 0 से शुरू करें, जब i < height, अपडेट करें (i को 1 से बढ़ाएं), करें:

  • j := 0 से शुरू करें, जब j < width, अपडेट करें (j को 1 से बढ़ाएं), करें:

    • sq[i mod n, j mod n] को 1 से बढ़ाएं

• एक ऐरे v परिभाषित करें

• i := 0 से शुरू करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें:

  • j := 0 से शुरू करें, जब j < n, अपडेट करें (j को 1 से बढ़ाएं), करें:

    • sq[i, j] को v के अंत में डालें

• ऐरे v को रिवर्स ऑर्डर में सॉर्ट करें

• i := 0, j := 0 से शुरू करें, जब i < v का आकार और j < maxOnes, अपडेट करें (i को 1 से बढ़ाएं), (j को 1 से बढ़ाएं), करें:

  • ret += v[i]

• ret लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

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

class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {
        int ret = 0;
        vector> sq(n, vector(n));
        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                sq[i % n][j % n]++;
            }
        }
        vector v;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                v.push_back(sq[i][j]);
            }
        }
        sort(v.rbegin(), v.rend());
        for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++) {
            ret += v[i];
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << (ob.maximumNumberOfOnes(3,3,2,1));
}

इनपुट

3, 3, 2, 1

आउटपुट

4