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.
Hey, Please share something about resources for learning competitive programming.
Please try to stick to the topic of the thread as far as possible.
Regarding your question, there are plenty of nice resources online, but in case you’re starting out, you can follow the resources listed here
thanks brother