C++ में सभी 1 वाले वर्गाकार उपमैट्रिक्स की गणना

मान लीजिए हमारे पास आकार m x n की एक बाइनरी मैट्रिक्स है। हमें सभी 1 वाले वर्गाकार उपमैट्रिक्स की संख्या गिननी है। इसलिए यदि मैट्रिक्स इस तरह है:

तो 15 वर्ग होंगे। एकल 1 के 10 वर्ग, चार 1 के 4 वर्ग, और नौ 1 का 1 वर्ग।

हल का दृष्टिकोण

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

• ans := 0, n := पंक्ति गिनती, m := स्तंभ गिनती सेट करें
• i = 0 से m-1 तक:
  • ans := ans + matrix[n-1][i]
• i = 0 से n-1 तक:
  • ans := ans + matrix[i][m-1]
• ans := ans - matrix[n-1][m-1]
• i = n-2 से 0 तक नीचे:
  • j = m-2 से 0 तक नीचे:
    • यदि matrix[i][j] == 1, तो:
      • matrix[i][j] := 1 + min(matrix[i+1][j+1], matrix[i][j+1], matrix[i+1][j]) का न्यूनतम
    • अन्यथा matrix[i][j] := 0
    • ans := ans + matrix[i][j]
• ans लौटाएं

उदाहरण

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

class Solution { 
public: 
    int countSquares(vector<vector<int>>& matrix) { 
        int ans = 0; 
        int n = matrix.size(); 
        int m = matrix[0].size(); 
        for(int i = 0; i < m; i++) ans += matrix[n-1][i]; 
        for(int i = 0; i < n; i++) ans += matrix[i][m-1]; 
        ans -= matrix[n-1][m-1]; 
        for(int i = n - 2; i >= 0; i--){ 
            for(int j = m - 2; j >= 0; j--){ 
                matrix[i][j] = matrix[i][j] == 1 ? 1 + min({matrix[i+1][j+1], matrix[i][j+1], matrix[i+1][j]}) : 0; 
                ans += matrix[i][j]; 
            } 
        } 
        return ans; 
    } 
}; 

int main(){ 
    vector<vector<int>> v = {{0,1,1,1},{1,1,1,1},{0,1,1,1}}; 
    Solution ob; 
    cout << (ob.countSquares(v)); 
}

इनपुट

[[0,1,1,1], [1,1,1,1], [0,1,1,1]]

आउटपुट

15