when visiting 0s the shortest path visiting all 1s in a binary matrix is allowed

The problem seems to be hard (pun intended) than I thought from the initial reading of it. This looks to me like a minimum cost Hamiltonian pathYou have to visit every vertex of an undirected graph with minimum total cost.

Suggested reading:

  1. The Minimum Flow Cost Hamiltonian Cycle Problem
  2. How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

I’ll let you know if I can think of a relatively easier solution.

The second example you gave is

1 1 1 1 0 0
0 0 0 1 0 0
1 1 1 1 0 1

The above can be translated to

enter image description here

enter image description here

Forming a graph from given matrix:

Treat every 1 as a node in a graph and there is an edge between adjacent vertices.

How to connect components?

Say C1 and C2 are two components. Find a pair <v1, v2> of vertices such that v1 belongs to C1, v2 belongs to C2 and distance between v1 & v2 is the least among all possible <v1, v2> pairs. How to find such pair? I’ll leave that as an exercise. Try it out. If unable to do it, let me know.

Compressing an edge:

With some more efforts you can “compress” the edges in the graph. By “compress” I mean all the chains could be represented as one node. I have tried to represent what a chain means in the images above with help of colors respectively. Compression is not necessary though a good optimization.

If a vertex is connected to more than two vertices, don’t include it in compression, for example the yellow node shown above. Notice that yellow node is connected to blue 1 because of component connection we discussed above.

If you are working with 0<=n, m <=30 constraint, you might not need to necessarily form a graph and compress it. As you say this question was asked during campus placement coding round, just try to work with the input matrix, submit and check if time limit exceeds. But during a face-to-face discussion, it might be expected to optimize by some means for example compression of edges is one optimization I could come up that could be helpful if graph contains chains or if number of 1s are less as compared to number of 0s – sparse matrix.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top