## 1277. Count Square Submatrices with All Ones

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.length <= 300`
• `0 <= arr[i][j] <= 1`

## Rust Solution

``````struct Solution;

impl Solution {
fn count_squares(mut matrix: Vec<Vec<i32>>) -> i32 {
let n = matrix.len();
let m = matrix.len();
let mut res = 0;
for i in 0..n {
for j in 0..m {
if matrix[i][j] == 1 {
matrix[i][j] = if i > 0 && j > 0 {
1 + [matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]]
.iter()
.min()
.unwrap()
} else {
1
};
}
res += matrix[i][j];
}
}
res
}
}
#[test]
fn test() {
let matrix = vec_vec_i32![[0, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]];
let res = 15;
assert_eq!(Solution::count_squares(matrix), res);
let matrix = vec_vec_i32![[1, 0, 1], [1, 1, 0], [1, 1, 0]];
let res = 7;
assert_eq!(Solution::count_squares(matrix), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.