1277. Count Square Submatrices with All Ones

public class Solution {
    public int CountSquares(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        int[,] dp = new int[m, n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        dp[i, j] = 1;
                    } else {
                        dp[i, j] = Math.Min(dp[i-1, j], Math.Min(dp[i, j-1], dp[i-1, j-1])) + 1;
                    }
                    count += dp[i, j];
                }
            }
        }
        return count;
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountSquares(int[][] matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int[,] dp = new int[m, n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        dp[i, j] = 1;
                    } else {
                        dp[i, j] = min(dp[i-1, j], min(dp[i, j-1], dp[i-1, j-1])) + 1;
                    }
                    count += dp[i, j];
                }
            }
        }
        return count;
    }
}

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int CountSquares(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[,] dp = new int[m, n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        dp[i, j] = 1;
                    } else {
                        dp[i, j] = Math.min(dp[i-1, j], Math.min(dp[i, j-1], dp[i-1, j-1])) + 1;
                    }
                    count += dp[i, j];
                }
            }
        }
        return count;
    }
}

var countSquares = function(matrix) {
    let m = matrix.length, n = matrix[0].length;
    let dp = Array.from({ length: m }, () => Array(n).fill(0));
    let count = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 1) {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
                count += dp[i][j];
            }
        }
    }

    return count;
};

def countSquares(matrix):
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    count = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                count += dp[i][j]
                
    return count

Algorithm

Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов.

Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц.

😎