PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
If you’re not familiar with minesweeper, you might want to play around with it before attempting this problem. Start by marking every cell with the number of neighbouring mines. Let’s take a look at what do these sets of simultaneously opened cells look like. Each such set consists of a connected component of zeroes and a set of cells a with positive number of neighbouring mines, which are the border of this connected component - let’s call them border cells. Clicking on some zero cell will close the connected component and its border. But if you click on some border cell, you might close several components and their borders. Therefore, it’s always optimal to aim for the border cells unless there is no border - be careful with entirely empty grids. You have no choice but to click on all cells which have no neighbouring zeros (this includes cells with mines).
You still have to choose minimum number of border cells to close all the components. This looks very much like the set covering problem. Next important observation is that each border cell can close at most 2 components. Try drawing a valid example with three components of zeroes around some positive cell and don’t forget that you have to include at least one mine in its neighbourhood. You can model this situation with a graph. Nodes represent components of zeroes and if it’s possible to close two components with a single click on some border cell, draw an edge between them. Notice the correspondence between a valid set of clicks and a matching in this graph. Look at it in the following way. You could use one click for every component. In comparisson, you can save one click by closing two components using a matched edge. What you’re looking for is a maximum matching in this general graph, which is easier said than done. The famous algorithm for general matchings is Edmonds’ blossom algorithm. It was probably a relief if you had a prewritten version. In case you don’t, it might be worth reading Gabow’s “Efficient Implementation of Edmonds’ Algorithm”.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here