you can solve it easily in O(mn). where m*n
is matrix dimension.
first consider only 1*T
type blocks.
iterate each row and in any row whenever you see a 0->1 consecutive element increase your block count by 1. (if first element of row is 1 then also increase count) similarly, do this on columns .
(here don't consider 1*11*1
blocks because that would already have been countedinitially in rowsany iteration. finally after iterating over all rows and columns. check for 1*1
blocks separately)