You're given a matrix, and all the elements in it is either 0 or 1.
What is considered as a submatrix is a matrix whose elements are all 0s.
For example, for given matrix
[ 0 0 1
0 0 0
1 0 1]
only one
|0| itself,

| 0 0 |,

| 0 |
| 0 |,

and

| 0 0 |
| 0 0 |

are both submatrixes, however something like
| 0 1 |
| 0 0 |
isn't a legal one.
How to find the total number of submatrixes?

Update:The interviewer gave me a hint that youcan use countSubstring for an array with 0s and 1s which return the number of legal substrings. The substring has similar definition as submatrix, consists of continuous 0 or 0s, without any 1.
I'll go through all the algorithm you provide today. Thank you all!