A bipartite matching between bomb position and rocks sud work i guess.
A greedy approach could be , find which cell destroys maximal numbers of rocks in each iteration until all are destroyed. But I cannot prove correctness.
The bipartite matching is actually between the rows and columns. Whenever you pick a cell you destroy all cells in that row and that column (or one matching). The maximum matching is equal to the minimum bombs used. You place an edge for each rock location (i,j) between row i and column j. (two sides of the bipartite matching)
I don't believe your greedy is optimal intuitively but I'm having difficult time forming a counterexample. I think the fastest solutions use this matching idea.
Excellent counter example, as for my bipartite matching idea I think it is incorrect as well because I messed up reducing this problem. My guess is the fast solutions are turning the dp solution into a bfs and not all states are then reached improving the average case or they are using branch and bound with the heuristic.
A greedy approach could be , find which cell destroys maximal numbers of rocks in each iteration until all are destroyed.
But I cannot prove correctness.
While the number of rocks is greater than 0
{
find max in matrix count[][]
bomb that possition
re-initilize\update count[][]
}
There's your greedy.
Complexity O(N^4) and since N<25 its no biggie.
Pretty sure there's no counter example for this.