# Finding the count of 0's bounded by all 1's

Given N * M 2-D matrix find out all the 0's which are completely bounded by the all 1's. ( This is not any online platform question ) (This problem statement I faced during an interview).

Sub-matrix or matrix which is forming the square or rectangular boundary should only contain 1 in it and 0's should inside that boundary.

Please refer examples for better understanding

Example:

Input : Row : 3 , Col : 3

1 1 1

1 0 1

1 1 1

Output : 1

Explanation : In above case only 3*3 matrix which have all 1's at there boundary and 1 zero enclosed within that.

Input : Row: 2 Col: 2

1 1

1 1

Output : 0

Input : Row: 4 Col: 4

1 0 1 0

1 1 1 0

1 0 1 1

1 1 1 1

Output : 1

Explanation : 0 based indexing i.e. sub-matrix (1,0) to (3 , 2 ) only sub-matrix which have 0 enclosed by all 1's. That's why output is 1.

Input : Row : 4 Col : 5

1 1 1 0 1

1 0 1 1 1

1 1 1 0 1

0 0 1 1 1

Output : 2

Explanation : Here sub-matrix ( 0 based indexing )

1. (0,0) to (2,2) has one(1) 0 enclosed.
2. (1,2) to (3,4) has one(1) 0 enclosed in it Therefore total count become 2.

Input : Row : 4 Col : 4

1 1 1 1

1 0 0 1

1 0 0 1

1 1 1 1

Output : 4

Explanation : Here matrix (0,0) to (3,3) contains four 0's enclosed within the 1's boundary. Therefore count is 4.

I have tried to solve this question but not able to think about the optimized solution.

My Algorithm ( Brute Force Algorithm ):

1. Generating the all the Sub-Matrix of a given matrix
2. Checking whether given sub-matrix satisfies my given condition or not.
3. Increment the counter repeat 1 to 3.