# Problem Approach

Can someone tell me the approach of this question

Give a 2D array of 1’s and 0’s, where 1denotes a person and 0 denotes a empty cell, find the minimum number of persons needs to be evacuated such that we can stop the spread of covid and maintain social distancing. If two 1’s are adjacent to each other column-wise or row-wise remove one of them and diagonally adjacent 1’s need not to be removed
Example: 1 1 0
1 1 1
1 1 1
Output: 0 1 0
1 0 1
0 1 0

Are you sure it’s dp ? As I think that you can simply find all the connected components and for each component just add \displaystyle \Bigl\lfloor \frac{S}{2} \Bigr \rfloor to the answer, where S is the size of the component

hii cubefreak777,
i am not able to understand why it’s always true??do u have some kind of proof??

No, it’s wrong, now that you’ve pointed out the correct solution would be as follows:
Iterate over all connected components and we can easily observe that cells of each connected component will make a bipartite graph, so just color each connected component black and white and then just take the min of number of white cells and black cells from each connected component and report the total sum as the result.

1 Like