Count Square Submatrices พร้อม All Ones ใน C++

สมมติว่าเราเป็นเมทริกซ์ไบนารี ขนาด m x n เราต้องนับจำนวนเมทริกซ์ย่อยกำลังสอง กับ 1 ทั้งหมด ดังนั้นหากเมทริกซ์เป็นเหมือน −

ดังนั้นจะมี 15 สี่เหลี่ยม ช่องสี่เหลี่ยม 10 ช่อง ช่อง 4 ช่อง 4 ช่อง และ 1 ช่อง ช่อง ช่อง 9 ช่อง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตั้งค่า 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
    • ถ้าเมทริกซ์[i, j] =1 แล้ว
      • เมทริกซ์[i, j] :=1 + ค่าต่ำสุดของ (เมทริกซ์[i + 1, j + 1], เมทริกซ์[i, j + 1], เมทริกซ์[i + 1, j])
    • มิฉะนั้น matrix[i,j] :=0
    • ans :=ans + matrix[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