Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix

Give a M x N binary matrix, replace all occurrences of 0 by 1 which are not completely surrounded by 1.


For example,

Input: 

[ 1  1  1  1  0  0  1  1  0  1 ]
[ 1  0  0  1  1  0  1  1  1  1 ]
[ 1  0  0  1  1  1  1  1  1  1 ]
[ 1  1  1  1  0  0  1  1  0  1 ]
[ 1  1  1  1  0  0  0  1  0  1 ]
[ 1  1  0  1  1  0  1  1  0  0 ]
[ 1  1  0  1  1  1  1  1  1  1 ]
[ 1  1  0  1  1  0  0  1  0  1 ]
[ 1  1  1  0  1  0  1  0  0  1 ]
[ 1  1  1  0  1  1  1  1  1  1 ]

Output: 
[ 1  1  1  1  1  1  1  1  1  1 ]
[ 1  0  0  1  1  1  1  1  1  1 ]
[ 1  0  0  1  1  1  1  1  1  1 ]
[ 1  1  1  1  0  0  1  1  1  1 ]
[ 1  1  1  1  0  0  0  1  1  1 ]
[ 1  1  1  1  1  0  1  1  1  1 ]
[ 1  1  1  1  1  1  1  1  1  1 ]
[ 1  1  1  1  1  0  0  1  0  1 ]
[ 1  1  1  1  1  0  1  0  0  1 ]
[ 1  1  1  1  1  1  1  1  1  1 ]

We can use DFS to solve this problem. The idea is to consider all zeroes present on the boundary of the matrix one by one and start a depth first search from them to replace all connected 0’s. Note that we don’t need a visited array here as we are replacing the value of every processed node and it won’t be considered again next time as it will have value 1.

 
C++ implementation –
 

Download   Run Code

Output:

1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 0 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 0 1 0 1
1 1 1 1 1 0 1 0 0 1
1 1 1 1 1 1 1 1 1 1

 

Time complexity of above solution is O(M*N).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
P G
Guest

It is very poorly worded. Just by reading title, you can misunderstand what is required to do.

wpDiscuz