ধরুন আমাদেরকে একটি ম্যাট্রিক্স দেওয়া হয়েছে যাতে মাত্র দুটি মান রয়েছে; 1s এবং 0s. আমাদের প্রদত্ত ম্যাট্রিক্সের সাবমেট্রিক্সের সংখ্যা খুঁজে বের করতে হবে যাতে সমস্ত 1s রয়েছে। আমরা আউটপুট হিসাবে মান প্রিন্ট করি।
সুতরাং, যদি ইনপুট মত হয়
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 |
তাহলে আউটপুট হবে 12।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=ম্যাট্রিক্সের আকার
- m :=ম্যাট্রিক্সের আকার[0]
- আকারের একটি অ্যারে যোগ সংজ্ঞায়িত করুন:n+1 x m+1।
- আরম্ভ করার জন্য i :=0, যখন i
- আরম্ভ করার জন্য j :=0, যখন j
- যোগ করুন[i + 1, j + 1] + =ম্যাট্রিক্স[i, j]
- add[i + 1, j + 1] + =add[i, j + 1]
- add[i + 1, j + 1] + =add[i + 1, j]
- add[i + 1, j + 1] - =add[i, j]
- আরম্ভ করার জন্য j :=0, যখন j
- নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
- করুন
- p :=0,
- q :=m - j;
- যখন p <=q, do −
- x :=(p + q) / 2
- a :=k * x
- cur :=add[i + k, j + x] - add[i, j + x] - add[i + k, j] + add[i, j]
- যদি cur এর সাথে a হয়, তাহলে −
- r :=x
- p :=x + 1
- অন্যথায়,
- q :=x - 1
- যদি r 0 এর সমান হয়, তাহলে −
- লুপ থেকে বেরিয়ে আসুন
- res :=res + r
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include<bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
int add[n + 1][m + 1];
memset(add, 0, sizeof(add));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
add[i + 1][j + 1] += matrix[i][j];
add[i + 1][j + 1] += add[i][j + 1];
add[i + 1][j + 1] += add[i + 1][j];
add[i + 1][j + 1] -= add[i][j];
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!matrix[i][j])
continue;
for (int k = 1; k <= (n - i); k++) {
int p = 0,
q = m - j;
int r;
while (p <= q) {
int x = (p + q) / 2;
int a = k * x;
int cur = add[i + k][j + x] - add[i][j + x] - add[i + k][j] + add[i][j];
if (cur == a) {
r = x;
p = x + 1;
} else
q = x - 1;
}
if (r == 0)
break;
res += r;
}
}
}
return res;
}
int main() {
vector<vector<int>> mat = {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}};
cout<< solve(mat) <<endl;
return 0;
} ইনপুট
{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}} আউটপুট
12
