C++-এ সব ১ সম্বহ একটি বর্গ উপম্যাট্রিক্স গণনা করুন

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে, আকার m x n। আমাদের সব ১ সম্বহ বর্গ উপম্যাট্রিক্সের সংখ্যা গণনা করতে হবে। যেন ম্যাট্রিক্সটি নিম্নরূপ হয় -

এখানে মোট ১৫টি বর্গ থাকবে। একক ১-এর ১০টি বর্গ, চার ১-এর ৪টি বর্গ, এবং নয় ১-এর ১টি বর্গ।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলো অনুসরণ করব -

• 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 + minimum of (matrix[i+1, j+1], matrix[i, j+1], matrix[i+1, j])
    • অন্যথায় matrix[i,j] := 0
    • ans := ans + matrix[i, j]
• ans রিটার্ন করুন

উদাহরণ (C++)

#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