Think of a graph with nodes corresponding to rows on the left and nodes corresponding co columns on the right.

Search about minimum vertex cover on bipartite, König's theorem.

Interesting part of this problem is that you shouldn't output the cardinality of MVC, but you should be able to recover the solution as well. Proof of König's theorem on Wikipedia already provides an efficient algorithm for retrieving that.