minimum-operations-to-remove-adjacent-ones-in-matrix

< Previous 　　　　　　　　　　　　　　　　 Next >

2123. Minimum Operations to Remove Adjacent Ones in Matrix (Hard)

Related Topics

[Graph] [Array] [Matrix]

Hints

Hint 1

Consider each cell containing a 1 as a vertex whose neighbors are the cells 4-directionally connected to it. The grid then becomes a bipartite graph.

Hint 2

You want to find the smallest set of vertices such that every edge in the graph has an endpoint in this set. If you remove every vertex in this set from the graph, then all the 1’s will be disconnected. Are there any well-known algorithms for finding this set?

Hint 3

This set of vertices is called a minimum vertex cover. You can find the size of a minimum vertex cover by finding the size of a maximum matching (Konig’s theorem).

Hint 4

There are well-known algorithms such as Kuhn’s algorithm and Hopcroft-Karp-Karzanov algorithm which can find a maximum matching in a bipartite graph quickly.