C++ এ সকলের সাথে স্কোয়ার সাবমেট্রিস গণনা করুন

ধরুন আমরা একটি বাইনারি ম্যাট্রিক্স, আকার m x n। আমাদের সমস্ত 1s সহ বর্গাকার সাবমেট্রিসের সংখ্যা গণনা করতে হবে। তাই ম্যাট্রিক্স যদি −

সুতরাং 15টি বর্গক্ষেত্র হবে। এককটির 10টি বর্গক্ষেত্র, চারটির 4টি বর্গক্ষেত্র এবং নয়টি সহ 1টি বর্গক্ষেত্র৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর সেট করুন :=0, n :=সারি গণনা এবং m :=কলাম গণনা
• আমি 0 থেকে m – 1
  পরিসরে
  • উত্তর :=উত্তর + ম্যাট্রিক্স[n – 1, i]
• আমি 0 থেকে n – 1
  পরিসরে
  • উত্তর :=উত্তর + ম্যাট্রিক্স[i, m – 1]
• উত্তর :=উত্তর – ম্যাট্রিক্স[n – 1, m - 1]
• আমি n – 2 থেকে 0
  রেঞ্জে
  • j-এর জন্য m – 2 থেকে 0
    রেঞ্জে
    • যদি ম্যাট্রিক্স[i, j] =1 হয়, তাহলে
      • ম্যাট্রিক্স[i, j] :=1 + সর্বনিম্ন (ম্যাট্রিক্স[i + 1, j + 1], ম্যাট্রিক্স[i, j + 1], ম্যাট্রিক্স[i + 1, j])
    • অন্যথায় ম্যাট্রিক্স[i,j] :=0
    • উত্তর :=উত্তর + ম্যাট্রিক্স[i, j]
• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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;
   }
};
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