C++ में गैर-शून्य सबमैट्रिक्स की संख्या ज्ञात करने का प्रोग्राम

मान लीजिए हमें एक मैट्रिक्स दिया गया है जिसमें केवल दो मान हैं: 1 और 0। हमें दिए गए मैट्रिक्स में उन सबमैट्रिक्स की संख्या ज्ञात करनी है जिनमें सभी 1 हैं। हम मान को आउटपुट के रूप में प्रिंट करते हैं।

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

तो आउटपुट 12 होगा।

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

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

• n := मैट्रिक्स का आकार
• m := मैट्रिक्स[0] का आकार
• आकार (n+1) x (m+1) का एक सरणी add परिभाषित करें
• i := 0 से n-1 तक:
  • j := 0 से m-1 तक:
    • 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]
• res := 0
• i := 0 से n-1 तक:
  • j := 0 से m-1 तक:
    • यदि matrix[i][j] शून्य है, तो अगले पुनरावृत्ति पर जाएं
    • k := 1 से (n - i) तक:
      • 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]
        • यदि cur == a:
          • r := x
          • p := x + 1
        • अन्यथा:
          • q := x - 1
      • यदि r == 0, तो लूप से बाहर निकलें
      • res := res + r
• res लौटाएं

उदाहरण

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

#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