-1
$\begingroup$

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.

Could anyone please help me out to think about more optimized approach to solve the above question ?

$\endgroup$
  • $\begingroup$ I find the problem statement unclear. What does "completely bounded by the all 1's" mean? Please edit to make it clearer what is the task you are trying to solve. Also, please credit the original source where you encountered this problem. $\endgroup$ – D.W. Feb 18 at 6:47
  • $\begingroup$ @D.W. I have modified the question with more explanation and added the source of the question also. Please let me know if I want to further edit it. I have given sufficient examples to explain the question. $\endgroup$ – Abhishek Tripathi Feb 18 at 16:44
0
$\begingroup$

Form a grid graph, with one vertex per cell. Add an edge between each pair of adjacent cells that contain a 0. Add one more start vertex, with an edge from it to every cell on the perimeter that contains a 0. Find all cells reachable from the start vertex (using DFS or BFS), and remove them. Then, count the number of remaining cells containing a 0.

$\endgroup$
  • $\begingroup$ Got your point. Thank you $\endgroup$ – Abhishek Tripathi Feb 21 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.