Count Square Submatrices with All Ones นับสี่เหลี่ยมจัตุรัสที่เป็น 1 ทั้งหมดใน C++

ให้เมทริกซ์ไบนารี m×n นับจำนวน square submatrices ที่ทุกค่าเป็น 1

ตัวอย่าง: [[0,1,1,1],[1,1,1,1],[0,1,1,1]] → 15 (10 ช่องเดี่ยว, 4 ช่อง 2×2, 1 ช่อง 3×3)

วิธีแก้ปัญหา (Dynamic Programming)

dp[i][j] = ขนาดสี่เหลี่ยมจัตุรัสสูงสุดที่มุมขวาล่างอยู่ที่ (i,j)

1. ans = 0
2. บวกขอบล่างและขอบขวาเข้า ans ก่อน (base case)
3. วนจากล่างขึ้นบน, ขวาไปซ้าย (i=n-2..0, j=m-2..0):
   • ถ้า matrix[i][j] == 1: matrix[i][j] = 1 + min(dp[i+1][j+1], dp[i][j+1], dp[i+1][j])
   • มิฉะนั้น: 0
   • ans += matrix[i][j]
4. คืนค่า 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);
    return 0;
}

Input

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

Output

15