title: Bomb dropping algorithm
body: <p>I have an <code>n x m</code> matrix consisting of non-negative integers. For example:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>"Dropping a bomb" decreases by one the number of the target cell and all eight of its neighbours, to a minimum of zero.</p>
  
  <pre><code>x x x 
  x X x
  x x x
  </code></pre>
  
  <p>What is an algorithm that would determine the minimum number of bombs required to reduce all the cells to zero?</p>
  
  <p><strong>B Option (Due to me not being a careful reader)</strong></p>
  
  <p>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:</p>
  
  <p>What about simple problem, when sequence in row must be non-increasing:</p>
  
  <p><code>8 7 6 6 5</code> is possible input sequence</p>
  
  <p><code>7 8 5 5 2</code> is not possible since 7 -> 8 growing in a sequence.</p>
  
  <p>Maybe finding answer for "easier" case would help in finding solution for harder one.</p>
  
  <p><strong>PS:</strong> 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?</p>