没有必要将问题转化为线性子问题。

相反，使用简单的贪婪启发式，即从最大的角落开始轰炸角落。

在给定的例子中，有四个角，{2,1,6,4}。对于每个角落，没有比轰炸单元格对角线更好的移动了，所以我们知道我们的第一个2+1+6+4 = 13次轰炸必须在这些对角线单元格中。在完成轰炸之后，我们会得到一个新的矩阵:

2 3 4 7 1      0 1 1 6 0      0 1 1 6 0     1 1 6 0     0 0 5     0 0 0 
1 5 2 6 2      0 3 0 5 1      0 3 0 5 1  => 1 0 4 0  => 0 0 3  => 0 0 0  
4 3 4 2 1      2 1 1 1 0      2 1 1 1 0     0 0 0 0     0 0 0     0 0 3  
2 1 2 4 1  =>  2 1 2 4 1  =>  2 1 2 4 1     0 0 3 0     0 0 3      
3 1 3 4 1      0 0 0 0 0      0 0 0 0 0 
2 1 4 3 2      0 0 0 0 0      0 0 0 0 0 
6 9 1 6 4      0 3 0 2 0      0 0 0 0 0 

在前13次爆炸之后，我们使用启发式方法通过3次爆炸消除3 0 2。现在，我们有两个新的角，在第四行{2,1}。我们炸了那些，再炸3次。我们现在已经将矩阵化简为4 * 4。有一个角落，左上角。我们搞砸了。现在我们还有两个角，{5,3}。因为5是最大的角，我们首先轰炸5个角，然后最后轰炸另一个角的3。总数是13+3+3+1+5+3 = 28。

永远不要轰炸边界(除非正方形没有边界以外的邻居) 零角落。 到零角，将对角线上一个正方形的角的值降低(唯一的非边界邻居) 这会产生新的角落。见第2节

编辑:没有注意到Kostek提出了几乎相同的方法，所以现在我提出了更强烈的主张: 如果要清除的角总是选择在最外层，那么它是最优的。

在OP的例子中:在除5之外的任何地方掉落2(1+1或2)并不会导致掉落5所能击中的任何方块。所以我们必须在5上加上2(在左下角加上6…)

在这之后，只有一种方法可以清除(在左上角)角落里原本是1(现在是0)的东西，那就是在B3上删除0(类似excel的符号)。 等等。

只有在清除了整个A和E列以及1和7行之后，才开始更深一层的清理。

考虑只清除那些故意清除的角落，清除0值的角落不需要花费任何成本，并且简化了思考。

因为所有以这种方式投掷的炸弹都必须被投掷，并且这将导致清除战场，这是最佳解决方案。

睡了一觉后，我意识到这不是真的。 考虑

  ABCDE    
1 01000
2 10000
3 00000
4 00000

我的方法是在B3和C2上投放炸弹，而在B2上投放炸弹就足够了

评价函数，总和:

int f (int ** matrix, int width, int height, int x, int y)
{
    int m[3][3] = { 0 };

    m[1][1] = matrix[x][y];
    if (x > 0) m[0][1] = matrix[x-1][y];
    if (x < width-1) m[2][1] = matrix[x+1][y];

    if (y > 0)
    {
        m[1][0] = matrix[x][y-1];
        if (x > 0) m[0][0] = matrix[x-1][y-1];
        if (x < width-1) m[2][0] = matrix[x+1][y-1];
    }

    if (y < height-1)
    {
        m[1][2] = matrix[x][y+1];
        if (x > 0) m[0][2] = matrix[x-1][y+1];
        if (x < width-1) m[2][2] = matrix[x+1][y+1];
    }

    return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2];
}

目标函数:

Point bestState (int ** matrix, int width, int height)
{
    Point p = new Point(0,0);
    int bestScore = 0;
    int b = 0;

    for (int i=0; i<width; i++)
        for (int j=0; j<height; j++)
        {
            b = f(matrix,width,height,i,j);

            if (b > bestScore)
            {
                bestScore = best;
                p = new Point(i,j);
            }
        }

    retunr p;
}

破坏功能:

void destroy (int ** matrix, int width, int height, Point p)
{
    int x = p.x;
    int y = p.y;

    if(matrix[x][y] > 0) matrix[x][y]--;
    if (x > 0) if(matrix[x-1][y] > 0) matrix[x-1][y]--;
    if (x < width-1) if(matrix[x+1][y] > 0) matrix[x+1][y]--;

    if (y > 0)
    {
        if(matrix[x][y-1] > 0) matrix[x][y-1]--;
        if (x > 0) if(matrix[x-1][y-1] > 0) matrix[x-1][y-1]--;
        if (x < width-1) if(matrix[x+1][y-1] > 0) matrix[x+1][y-1]--;
    }

    if (y < height-1)
    {
        if(matrix[x][y] > 0) matrix[x][y+1]--;
        if (x > 0) if(matrix[x-1][y+1] > 0) matrix[x-1][y+1]--;
        if (x < width-1) if(matrix[x+1][y+1] > 0) matrix[x+1][y+1]--;
    }
}

目标函数:

bool isGoal (int ** matrix, int width, int height)
{
    for (int i=0; i<width; i++)
        for (int j=0; j<height; j++)
            if (matrix[i][j] > 0)
                return false;
    return true;
}

线性最大化函数:

void solve (int ** matrix, int width, int height)
{
    while (!isGoal(matrix,width,height))
    {
        destroy(matrix,width,height, bestState(matrix,width,height));
    }
}

这不是最优的，但可以通过找到更好的评价函数来优化。

. .但是考虑到这个问题，我在想一个主要的问题是在0中间的某个点上得到废弃的数字，所以我要采取另一种方法。这是支配最小值为零，然后试图转义零，这导致一般的最小现有值(s)或这样

这是一个广度搜索，通过这个“迷宫”的位置寻找最短路径(一系列轰炸)。不，我不能证明没有更快的算法，抱歉。

#!/usr/bin/env python

M = ((1,2,3,4),
     (2,3,4,5),
     (5,2,7,4),
     (2,3,5,8))

def eachPossibleMove(m):
  for y in range(1, len(m)-1):
    for x in range(1, len(m[0])-1):
      if (0 == m[y-1][x-1] == m[y-1][x] == m[y-1][x+1] ==
               m[y][x-1]   == m[y][x]   == m[y][x+1] ==
               m[y+1][x-1] == m[y+1][x] == m[y+1][x+1]):
        continue
      yield x, y

def bomb(m, (mx, my)):
  return tuple(tuple(max(0, m[y][x]-1)
      if mx-1 <= x <= mx+1 and my-1 <= y <= my+1
      else m[y][x]
      for x in range(len(m[y])))
    for y in range(len(m)))

def findFirstSolution(m, path=[]):
#  print path
#  print m
  if sum(map(sum, m)) == 0:  # empty?
    return path
  for move in eachPossibleMove(m):
    return findFirstSolution(bomb(m, move), path + [ move ])

def findShortestSolution(m):
  black = {}
  nextWhite = { m: [] }
  while nextWhite:
    white = nextWhite
    nextWhite = {}
    for position, path in white.iteritems():
      for move in eachPossibleMove(position):
        nextPosition = bomb(position, move)
        nextPath = path + [ move ]
        if sum(map(sum, nextPosition)) == 0:  # empty?
          return nextPath
        if nextPosition in black or nextPosition in white:
          continue  # ignore, found that one before
        nextWhite[nextPosition] = nextPath

def main(argv):
  if argv[1] == 'first':
    print findFirstSolution(M)
  elif argv[1] == 'shortest':
    print findShortestSolution(M)
  else:
    raise NotImplementedError(argv[1])

if __name__ == '__main__':
  import sys
  sys.exit(main(sys.argv))

对于更新后的问题，简单的贪心算法可以得到最优结果。

向单元格A[1,1]投掷A[0,0]炸弹，然后向单元格A[2,1]投掷A[1,0]炸弹，并继续向下此过程。要清除左下角，向单元格A[n -2,1]投掷max(A[n -1,0]， A[n -2,0]， A[n -3,0])炸弹。这将完全清除前3列。

用同样的方法清除第3、4、5列，然后是第6、7、8列，等等。

不幸的是，这并不能帮助找到最初问题的解决方案。

“更大”的问题(没有“非增加”约束)可能被证明是np困难的。这是证明的草图。

假设我们有一个度为3的平面图形。我们来求这个图的最小顶点覆盖。根据维基百科的文章，这个问题对于3次以下的平面图形是np困难的。这可以通过平面3SAT的简化来证明。平面3SAT的硬度由3SAT降低而成。这两个证明都在Erik Demaine教授最近的“算法下界”讲座(第7和第9讲)中提出。

如果我们分割原始图的一些边(图中左边的图)，每条边都有偶数个额外的节点，结果图(图中右边的图)应该对原始顶点具有完全相同的最小顶点覆盖。这样的转换允许将图顶点对齐到网格上的任意位置。

如果我们将图顶点只放置在偶数行和列上(这样就不会有两条边与一个顶点形成锐角)，在有边的地方插入“1”，在其他网格位置插入“0”，我们可以使用原始问题的任何解决方案来找到最小顶点覆盖。

这里有一个解决方案，推广良好的性质的角。

让我们假设我们可以为给定的字段找到一个完美的落点，也就是说，一个减少其中值的最佳方法。然后，为了找到最少的炸弹数量，一个算法的初稿可能是(代码是从ruby实现中复制粘贴的):

dropped_bomb_count = 0
while there_are_cells_with_non_zero_count_left
  coordinates = choose_a_perfect_drop_point
  drop_bomb(coordinates)
  dropped_bomb_count += 1
end
return dropped_bomb_count

挑战是choose_a_perfect_drop_point。首先，让我们定义一个完美的落点是什么。

(x, y)的放置点会减少(x, y)中的值。它也可能会减少其他单元格中的值。 (x, y)的放置点A比(x, y)的放置点b更好，如果它减少了b所减少的单元格的适当超集中的值。 如果没有其他更好的投放点，投放点是最大的。 (x, y)的两个放置点是等效的，如果它们减少了同一组单元格。 如果(x, y)的放置点等价于(x, y)的所有最大放置点，那么它就是完美的。

如果(x, y)存在一个完美的投放点，那么您不能比在(x, y)的一个完美投放点上投放炸弹更有效地降低(x, y)处的值。

给定字段的完美放置点是其任何单元格的完美放置点。

以下是一些例子:

1 0 1 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0

单元格(0,0)(从零开始的索引)的完美放置点是(1,1)。(1,1)的所有其他放置点，即(0,0)、(0,1)和(1,0)，减少的单元格较少。

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

单元格(2,2)(从零开始的索引)的完美落点是(2,2)，以及所有周围的单元格(1,1)、(1,2)、(1,3)、(2,1)、(2,3)、(3,1)、(3,2)和(3,3)。

0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

单元格(2,2)的完美放置点是(3,1):它减少了(2,2)中的值和(4,0)中的值。(2,2)的所有其他放置点都不是最大的，因为它们减少了一个单元格。(2,2)的完美下拉点也是(4,0)的完美下拉点，它是字段的唯一完美下拉点。它为这个领域带来了完美的解决方案(一颗炸弹)。

1 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
1 0 0 0 0

(2,2)没有完美的落点:(1,1)和(1,3)都减少(2,2)和另一个单元格(它们是(2,2)的最大落点)，但它们不相等。然而，(1,1)是(0,0)的完美落点，(1,3)是(0,4)的完美落点。

根据完美落点的定义和一定的检查顺序，我得到了以下问题示例的结果:

Drop bomb on 1, 1
Drop bomb on 1, 1
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 6
Drop bomb on 1, 2
Drop bomb on 1, 2
Drop bomb on 0, 6
Drop bomb on 0, 6
Drop bomb on 2, 1
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 3, 1
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 4
Drop bomb on 3, 4
Drop bomb on 3, 3
Drop bomb on 3, 3
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 4, 6
28

然而，该算法只有在每一步之后至少有一个完美落点时才能工作。可以在没有完美落点的情况下构建例子:

0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

对于这些情况，我们可以修改算法，这样我们就不会选择完美的落点，而是选择一个具有最大落点的最小选择的坐标，然后计算每个选择的最小值。在上面的例子中，所有有值的单元格都有两个最大落点。例如，(0,1)有最大落点(1,1)和(1,2)。选择其中任何一个，然后计算最小值，会得到这样的结果:

Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2