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.

Hi EveryOne,

I was trying to solve EPALIN problem of SPOJ using Z Algorithm(Z Function). But i don't know why am i getting TLE on this.

My Solution link: http://ideone.com/k38SUX