Given a 2D array of Os and Xs, find the minimum number of Os that need to be flipped into Xs to connect all the Xs connected. An X is connected to another Xs if they are adjacent to each other(Not diagonally).
Sample input:
A =
[ OOOXOOO
OOXXOXO
OXOOOXO ]
Output : 2
The idea I had in my mind was choosing an X and then keep on travelling to the nearest X while flipping the Os in between till we connect all the Xs. Is anything wrong with this or can you suggest a better approach?
Also, is this similar to finding the Minimum Spanning tree using Kruskal's Aglo or Prim's Algo?