मान लीजिए हमें एक मैट्रिक्स दिया गया है जिसमें केवल दो मान हैं; 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]
- जोड़ें [i + 1, j + 1] + =जोड़ें [i, j + 1]
- जोड़ें [i + 1, j + 1] + =जोड़ें [i + 1, j]
- जोड़ें [i + 1, j + 1] - =जोड़ें [i, j]
- इनिशियलाइज़ j :=0 के लिए, जब j
- निम्न भाग पर ध्यान न दें, अगले भाग पर जाएं
- करें
- p :=0,
- q :=m - j;
- जबकि p <=q, −
- . करें
- x :=(p + q) / 2
- a :=k * x
- cur :=add[i + k, j + x] - add[i, j + x] - add[i + k, j] + add[i, j]
- यदि वक्र एक के समान है, तो −
- r :=x
- p :=x + 1
- अन्यथा,
- q :=x - 1
- यदि r, 0 के समान है, तो −
- लूप से बाहर आएं
- रेस:=रेस + आर
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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
