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.

for example:

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.