ধরা যাক M হল একটি w x h ডাইমেনশনের ম্যাট্রিক্স, যাতে প্রতিটি সেলের মান ০ বা ১, এবং M-এর যেকোনো l x l আকারের স্কয়ার সাব-ম্যাট্রিক্সে সর্বোচ্চ maxOnes সংখ্যক ১ থাকে। আমাদের ম্যাট্রিক্স M-এর সর্বোচ্চ সম্ভাব্য ১-এর সংখ্যা খুঁজে বের করতে হবে।
তাই, যদি ইনপুট w = 3, h = 3, l = 2, maxOnes = 1 হয়, তবে আউটপুট হবে 4 কারণ ৩*৩ ম্যাট্রিক্সে, কোনো ২*২ সাব-ম্যাট্রিক্সে ১-এর চেয়ে বেশি ১ থাকতে পারবে না। ৪টি ১ সহ সেরা সমাধান হল -
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
এটি সমাধান করতে, আমরা নিচের ধাপগুলো অনুসরণ করব -
ret := 0
আকার n x n-এর একটি 2D অ্যারে sq বানান
i := 0 থেকে শুরু করুন, যখন i < height, (i ১ করে বাড়ান), করুন -
j := 0 থেকে শুরু করুন, যখন j < width, (j ১ করে বাড়ান), করুন -
sq[i mod n, j mod n] ১ করে বাড়ান
একটি অ্যারে v ডিফাইন করুন
i := 0 থেকে শুরু করুন, যখন i < n, (i ১ করে বাড়ান), করুন -
j := 0 থেকে শুরু করুন, যখন j < n, (j ১ করে বাড়ান), করুন -
sq[i, j] v-এর শেষে ইনসার্ট করুন
অ্যারে vকে রিভার্স অর্ডারে সর্ট করুন
i := 0, j := 0 থেকে শুরু করুন, যখন i < v-এর আকার এবং j < maxOnes, (i ১ করে বাড়ান), (j ১ করে বাড়ান), করুন -
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 < vector <int> > sq(n, vector <int>(n)); for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ sq[i % n][j % n]++; } } vector <int> 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; } }; main(){ Solution ob; cout << (ob.maximumNumberOfOnes(3,3,2,1)); }
ইনপুট
3, 3, 2, 1
আউটপুট
4
