En este artículo, discutimos un problema interesante que requiere contar el número de submatrices cuadradas con todos sus elementos como ‘1’ en una matriz de unos y ceros. Es un problema común que aparece en plataformas de codificación competitiva como LeetCode y está categorizado bajo problemas de programación dinámica.
Descripción del Problema
Dada una matriz de dimensiones m x n que contiene solo unos y ceros, queremos determinar cuántas submatrices cuadradas existen donde todos los elementos son unos.Solución
Para resolver este problema, utilizamos un enfoque de programación dinámica. Crearemos una matrix auxiliar DP que almacenará el tamaño máximo del cuadrado que tiene su esquina inferior derecha en una posición dada. La idea es sencilla: si encontramos un ‘1’ en la posición (i, j), calculamos el tamaño máximo del cuadrado usando la relación de recurrencia basada en sus vecinos arriba, izquierda y diagonal superior izquierda.Paso a Paso
- Crear una matriz DP del mismo tamaño que el input matrix y rellenarla con ceros.
- Iterar sobre cada elemento del matrix. Si un elemento es ‘1’, calculamos el valor DP usando:
DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1
- Sumamos los valores en la matriz DP para obtener el total de submatrices cuadradas.
public class CountSquares {
public int countSquares(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
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; // Edges can only form 1x1 squares
} else {
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
count += dp[i][j];
}
}
}
return count;
}
}