# 1277. Count Square Submatrices with All Oness

Contents

Problem solution 1277 “Count Square Submatrices with All Oness” from LeetCode.

## Problem

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Constraints:

• 1 <= `len(arr)` <= 300
• 1 <= `len(arr[0])` <= 300
• 0 <= `arr[i][j]` <= 1

### example

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````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. ``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````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. ``````

## Solution

### DFS

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 `````` ``````func countSquares(matrix [][]int) int { sum:=0 for i:=range matrix { for j:=range matrix[i] { sum+=helper(matrix, i, j, 0) } } return sum } func helper(m [][]int, i,j,l int) int { if i>=len(m) || j>=len(m[0] ) { return 0 } if m[i][j] == 0 { return 0 } sum := 0 f := true for idx:=1; idx<=l;idx++ { f = f && i-idx>=0 && j-idx>=0 &&m[i-idx][j] == 1 &&m[i][j-idx] == 1 } if f { sum++ sum += helper(m,i+1,j+1,l+1) } return sum } ``````