1277.js

/** ------------------------------------------------------------------------------
 * 
 * 1277. Count Square Submatrices with All Ones
 * Topics: DP, Matrix
 * https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/?envType=daily-question&envId=2024-10-27
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var countSquares = function (matrix) {
  const row = matrix.length
  const col = matrix[0].length

  let count = 0

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (matrix[i][j] === 0) continue
      if (i > 0 && j > 0) {
        matrix[i][j] += Math.min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1])
      }
      count += matrix[i][j]
    }
  }

  return count
}

var countSquares = function (matrix) {
  const dp = []
  for (let i = 0; i < matrix.length; i++) {
    dp.push([])
  }

  dp[0][0] = matrix[0][0]
  let total = dp[0][0]
  for (let i = 1; i < matrix.length; i++) {
    dp[i][0] = matrix[i][0]
    total += dp[i][0]
  }

  for (let j = 1; j < matrix[0].length; j++) {
    dp[0][j] = matrix[0][j]
    total += dp[0][j]
  }

  for (let i = 1; i < matrix.length; i++) {
    for (let j = 1; j < matrix[0].length; j++) {
      if (matrix[i][j] === 0) {
        dp[i][j] = 0
      } else {
        dp[i][j] = 1
        dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
      }
      total += dp[i][j]
    }
  }
  return total
}

console.log(
  countSquares([
    [0, 1, 1, 1],
    [1, 1, 1, 1],
    [0, 1, 1, 1],
  ]),
)