# ---
# title: 1277. Count Square Submatrices with All Ones
# id: problem1277
# author: Tian Jun
# date: 2020-10-31
# difficulty: Medium
# categories: Array, Dynamic Programming
# link: <https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/>
# hidden: true
# ---
# 
# Given a `m * n` matrix of ones and zeros, return how many **square**
# submatrices have all ones.
# 
# 
# 
# **Example 1:**
# 
#     
#     
#     Input: matrix =
#     [
#       [0,1,1,1],
#       [1,1,1,1],
#       [0,1,1,1]
#     ]
#     Output: 15
#     Explanation: 
#     There are **10** squares of side 1.
#     There are **4** squares of side 2.
#     There is  **1** square of side 3.
#     Total number of squares = 10 + 4 + 1 = **15**.
#     
# 
# **Example 2:**
# 
#     
#     
#     Input: matrix = 
#     [
#       [1,0,1],
#       [1,1,0],
#       [1,1,0]
#     ]
#     Output: 7
#     Explanation: 
#     There are **6** squares of side 1.  
#     There is **1** square of side 2. 
#     Total number of squares = 6 + 1 = **7**.
#     
# 
# 
# 
# **Constraints:**
# 
#   * `1 <= arr.length <= 300`
#   * `1 <= arr[0].length <= 300`
#   * `0 <= arr[i][j] <= 1`
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
