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 1Minimum 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.
The problem can be solved using minimum spanning tree algorithms.
First of all let's consider all the separate connected components as separate nodes.
Now from each of the nodes make an edge with all the other nodes, the cost of this edge will be the minimum number of cells we need to modify to make them connected. Which can be done using BFS/DFS.
Now run any MST algorithms in the current graph. It'll give you the minimum cost you need to connect all the nodes.
Note : The complexity will be O((N^2)logN). Where N is the number of cell in the matrix. There may have some other solutions better than this.
Hello,
I don't think this approach would work — The problem is that you can use some "1" you used during connecting.
lets consider following grid:
The MST algorithm will see all possibilities of length "1", so it will say "3". Yet the path between two nodes will be used for each of those connections so the answer will be just "1".
Once we were discussing it and we came to conclusion that exponential solution might be needed (yet I hope someone will correct me and find something better ^_^ )
Good Luck & Have Nice Day
My bad. You are right. Mst approach won't work here.
If I understood the problem correctly, you would want the minimum number of cells to change in order to make the figure 8-connected.
In the 4-connected case (up-down-left-right), the problem is called Rectilinear Steiner Tree, and it is a well established fact that it is NP hard (you can find it on Wikipedia for sure). I don't know the exact proof for that, but I suppose you could apply the same logic to deduce that this one is also NP hard.
I found the problem here which asks for the minimum number of operators changing 0-cell to 1-cell in a binary grid so that all pairwise 1-cell vertices can reach to each other through 1-cell neighbors (sharing edges).
The constraints are $$$1 \leq w, h \leq 15$$$, time limit $$$0.5s$$$.
(Unfortunately, this site does not allow me to submit.)
Does anyone know how to solve this problem?
I would try solving it using dp by broken profile. However, here you have to also keep the information about the connected components in the profile. This means that there will be more than $$$2^n$$$ possible states, but still rather few.
At every step adding a 1 cell can either create a new connected component, extend one connected component, or merge two connected components.
The complexity would be $$$O(n^2 * P(n))$$$, where $$$P(n)$$$ would be the number of states (profiles). Probably better solutions exist, but I feel this will pass TL if coded carefully.
One can solve the problem here
It is totally different.