Bomb dropping algorithm
I have an n x m matrix consisting of non-negative integers. For example:
2 3 4 7 1
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
6 9 1 6 4
"Dropping a bomb" decreases by one the number of the target cell and all eight of its neighbours, to a minimum of zero.
x x x
x X x
x x x
What is an algorithm that would determine the minimum number of bombs required to reduce all the cells to zero?
B Option (Due to me not being a careful reader)
Actually the first version of problem is not the one I'm seeking answer for. I didn't carefully read whole task, there's additional constraints, let us say:
What about simple problem, when sequence in row must be non-increasing:
8 7 6 6 5 is possible input sequence
7 8 5 5 2 is not possible since 7 -> 8 growing in a sequence.
Maybe finding answer for "easier" case would help in finding solution for harder one.
PS: I believe that when we have several same situations require minimum bombs to clear upper line, we choose one that use most bombs on "left side" of the row. Still any proof that might be correct?
Answer
There is a way to reduce this to a simple sub-problem.
There are 2 parts to the explanation, the algorithm, and the reason the algorithm provides an optimal solution. The first won't make sense without the second, so I'll start with the why.
If you think of bombing the rectangle (assume a big rectangle - no edge cases yet) you can see that the only way to reduce the hollow rectangle of squares on the perimeter to 0 is to bomb either the perimeter or to bomb the hollow rectangle of squares just inside the perimeter. I'll call the perimeter layer 1, and the rectangle inside it layer 2.
An important insight is that there is no point bombing layer 1, because the "blast radius" you get from doing so is always contained within the blast radius of another square from layer 2. You should be able to easily convince yourself of this.
So, we can reduce the problem to finding an optimal way to bomb away the perimeter, then we can repeat that until all squares are 0.
But of course, that won't always find an optimal solution if it's possible to bomb away the perimeter in a less than optimal fashion, but by using X extra bombs make the problem of reducing the inner layer simpler by >X bombs. So, if we call the permiter layer one, if we place an extra X bombs somewhere in layer 2 (just inside layer 1), can we reduce the effort of later bombing away layer 2 by more than X? In other words, we have to prove we can be greedy in reducing the outer perimeter.
But, we do know we can be greedy. Because no bomb in layer 2 can ever be more efficient in reducing layer 2 to 0 than a strategically placed bomb in layer 3. And for the same reason as before - there is always a bomb we can place in layer 3 that will affect every square of layer 2 that a bomb placed in layer 2 can. So, it can never harm us to be greedy (in this sense of greedy).
So, all we have to do is find the optimal way to reduce the permiter to 0 by bombing the next inner layer.
We are never hurt by first bombing the corner to 0, because only the corner of the inner layer can reach it, so we really have no choice (and, any bomb on the perimeter that can reach the corner has a blast radius contained in the blast radius from the corner of the inner layer).
Once we have done so, the squares on the perimeter adjacent to the 0 corner can only be reached by 2 squares from the inner layer:
0 A B
C X Y
D Z
At this point the perimeter is effectively a closed 1 dimensional loop, because any bomb will reduce 3 adjacent squares. Except for some weirdness near the corners - X can "hit" A,B,C,and D.
Now we can't use any blast radius tricks - the situation of each square is symmetric, except for the weird corners, and even there no blast radius is a subset of another. Note that if this were a line (as Colonel Panic discusses) instead of a closed loop the solution is trivial. The end points must be reduced to 0, and it never harms you to bomb the points adjacent to the end points, again because the blast radius is a superset. Once you have made your endpoint 0, you still have a new endpoint, so repeat (until the line is all 0).
So, if we can optimally reduce a single square in the layer to 0 we have an algorithm (because we have cut the loop and now have a straight line with endpoints). I believe bombing adjacent to the square with the lowest value (giving you 2 options) such that the highest value within 2 squares of that lowest value is the minimum possible (you may have to split your bombing to manage this) will be optimal but I don't (yet?) have a proof.