A Matrix containing 0s and 1s is provided, all 0s are water and 1s are land. A group of connected 1s forms an island. If one change can convert one 0 to 1 then find out minimum number of changes that we need to make so that there will be only one island in matrix.
1 0 1 0 0 0 1 0 1
Minimum number of changes to convert into single island is 1. Convert (2,2) to 1.
I was asked this question in an interview. I used dfs to find out the number of islands. But can't get an approach to solve further.