有一种方法可以把这个问题简化为一个简单的子问题。

解释分为两部分，算法和算法的原因 提供最优解决方案。没有第二个，第一个就说不通了，所以我 从为什么开始。

如果你想轰炸矩形(假设一个大矩形-还没有边缘情况) 你可以看到，只有这样才能减少空心矩形上的正方形 周长到0的意思是炸毁周长或者炸毁的空心矩形 就在外围的方块里。我称周长为图层1，其中的矩形为图层2。

一个重要的观点是，没有点轰炸层1，因为 你这样做得到的“爆炸半径”总是包含在爆炸半径内 另一个来自第2层的正方形。你应该很容易就能说服自己。

所以，我们可以把问题简化为找到一个最优的方法来炸开周长，然后我们可以重复这个过程，直到所有的平方都为0。

但当然了，如果有爆炸的可能，并不总能找到最优解 以一种不太理想的方式远离周边，但通过使用X个额外的炸弹制造 用>X炸弹减少内层的问题。如果我们调用 第一层，如果我们在第二层的某个地方放置一个额外的X炸弹(只是 在第1层内，我们可以减少之后轰炸第2层的努力吗 X ?换句话说，我们必须证明我们可以贪心化简外部 周长。

但是，我们知道我们可以贪婪。因为第2层的炸弹永远不会更多 有效减少第2层到0比战略上放置炸弹在第3层。和 因为和之前一样的原因-总有一个炸弹我们可以放在第3层 将影响第2层的每一个方块，炸弹放在第2层可以。所以，它可以 永远不要伤害我们的贪婪(在这个意义上的贪婪)。

所以，我们要做的就是找到最优的方法，通过轰炸将许可值降为0 下一个内层。

我们永远不会因为先把角落炸到0而受伤，因为只有内层的角落可以到达，所以我们真的没有选择(并且，任何可以到达角落的周长炸弹的爆炸半径都包含在内层角落的爆炸半径中)。

一旦我们这样做了，与0角相邻的周长上的正方形只能由内层的2个正方形到达:

0       A       B

C       X       Y

D       Z

在这一点上，周长实际上是一个封闭的1维环，因为任何炸弹都会减少3个相邻的正方形。除了角落附近的一些奇怪之处——X可以“击中”A、B、C和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).

所以，如果我们可以优化地将层中的单个正方形减少到0，我们就有了一个算法(因为我们已经切断了循环，现在有了一条带有端点的直线)。我相信轰炸与最小值相邻的正方形(给你2个选项)，这样在最小值的2个正方形内的最大值就是最小值(你可能不得不分割你的轰炸来管理这一点)将是最优的，但我还没有证明。

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

让我们假设我们可以为给定的字段找到一个完美的落点，也就是说，一个减少其中值的最佳方法。然后，为了找到最少的炸弹数量，一个算法的初稿可能是(代码是从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

Pólya说:“如果你不能解决一个问题，那么有一个更容易解决的问题:找到它。”

显然更简单的问题是一维问题(当网格是单行时)。让我们从最简单的算法开始——贪婪地轰炸最大的目标。什么时候会出问题?

给定11 11，贪婪算法对先炸毁哪个单元格无关。当然，中心单元格更好——它一次将所有三个单元格归零。这就提出了一种新的算法a，“炸弹最小化剩余的总和”。这个算法什么时候会出错?

给定1 1 2 11 1，算法A在轰炸第2，第3或第4单元格之间是无所谓的。但是轰炸第二个单元格，留下0 0 11 11比轰炸第三个单元格，留下10 10 10 10 1好。如何解决这个问题?轰炸第三个单元格的问题是，左边的功和右边的功必须分开做。

“炸弹使剩余的总和最小化，但使左边(我们轰炸的地方)的最小值和右边的最小值最大化”如何?叫这个算法b，这个算法什么时候出错?

编辑:在阅读了评论之后，我同意一个更有趣的问题将是改变一维问题，使其两端连接起来。很乐意看到这方面的进展。

生成最慢但最简单且无错误的算法，并测试所有有效的可能性。这种情况非常简单(因为结果与炸弹放置的顺序无关)。

创建N次应用bomp的函数 为所有炸弹放置/炸弹计数可能性创建循环(当矩阵==0时停止) 记住最好的解决方案。 在循环的最后，你得到了最好的解决方案 不仅是炸弹的数量，还有它们的位置

代码可以是这样的:

void copy(int **A,int **B,int m,int n)
    {
    for (int i=0;i<m;i++)
     for (int j=0;i<n;j++)
       A[i][j]=B[i][j];
    }

bool is_zero(int **M,int m,int n)
    {
    for (int i=0;i<m;i++)
     for (int j=0;i<n;j++)
      if (M[i][j]) return 0;
    return 1;
    }

void drop_bomb(int **M,int m,int n,int i,int j,int N)
    {
    int ii,jj;
    ii=i-1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i-1; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i-1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    }

void solve_problem(int **M,int m,int n)
    {
    int i,j,k,max=0;
    // you probably will need to allocate matrices P,TP,TM yourself instead of this:
    int P[m][n],min;             // solution: placement,min bomb count
    int TM[m][n],TP[m][n],cnt;   // temp
    for (i=0;i<m;i++)            // max count of bomb necessary to test
     for (j=0;j<n;j++)
      if (max<M[i][j]) max=M[i][j];
    for (i=0;i<m;i++)            // reset solution
     for (j=0;j<n;j++)
      P[i][j]=max;
    min=m*n*max; 
        copy(TP,P,m,n); cnt=min;

    for (;;)  // generate all possibilities
        {
        copy(TM,M,m,n);
        for (i=0;i<m;i++)   // test solution
         for (j=0;j<n;j++)
          drop_bomb(TM,m,n,TP[i][j]);
        if (is_zero(TM,m,n))// is solution
         if (min>cnt)       // is better solution -> store it
            {
            copy(P,TP,m,n); 
            min=cnt;    
            }
        // go to next possibility
        for (i=0,j=0;;)
            {
            TP[i][j]--;
            if (TP[i][j]>=0) break;
            TP[i][j]=max;
                 i++; if (i<m) break;
            i=0; j++; if (j<n) break;
            break;
            }
        if (is_zero(TP,m,n)) break;
        }
    //result is in P,min
    }

这可以通过很多方式进行优化，……最简单的是用M矩阵重置解，但你需要改变最大值和TP[][]递减代码

这将是一个贪婪的方法:

计算一个阶为n X m的“score”矩阵，其中score[i][j]是如果位置(i,j)被炸毁，则矩阵中各点的总扣除额。(一个点的最高分数是9分，最低分数是0分) 逐行移动，找到并选择第一个得分最高的位置(例如(i,j))。 炸弹(i, j)。增加炸弹数量。 如果原矩阵的所有元素都不为零，则转到1。

但我怀疑这是否是最佳解决方案。

编辑:

我上面提到的贪心方法，虽然有效，但很可能不能给我们最优的解决方案。所以我想应该添加一些DP的元素。

我想我们可以同意，在任何时候，具有最高“分数”(分数[I][j] =总扣分，如果(I,j)被炸)的位置之一必须被瞄准。从这个假设开始，下面是新的方法:

NumOfBombs(M):(返回所需的最小炸弹数量)

给定一个矩阵M (n X M)，如果M中的所有元素都为0，则返回0。 计算“分数”矩阵M。 设k个不同的位置P1 P2…Pk (1 <= k <= n*m)，为m中得分最高的位置。 return (1 + min(NumOfBombs(M1)， NumOfBombs(M2)，…， NumOfBombs(Mk)) M1, M2,……，Mk是我们轰炸位置P1, P2，…， Pk。

此外，如果我们想在此基础上破坏位置的顺序，我们必须跟踪“min”的结果。

由于时间不够，我不得不停留在部分解决方案上，但希望即使是这个部分解决方案也能提供解决这个问题的潜在方法的一些见解。

当面对一个困难的问题时，我喜欢想出一些简单的问题来培养对问题空间的直觉。这里，我采取的第一步是将这个二维问题简化为一维问题。考虑一行字:

0 4 2 1 3 0 1

不管怎样，你知道你需要在4点附近炸4次才能把它降到0。因为左边是一个较低的数字，所以轰炸0或4比轰炸2没有任何好处。事实上，我相信(但缺乏严格的证明)轰炸2，直到4点降到0，至少和任何其他策略一样好，让4点降到0。从左到右，我们可以采用如下策略:

index = 1
while index < line_length
  while number_at_index(index - 1) > 0
    bomb(index)
  end
  index++
end
# take care of the end of the line
while number_at_index(index - 1) > 0
  bomb(index - 1)
end

几个轰炸命令示例:

0 4[2]1 3 0 1
0 3[1]0 3 0 1
0 2[0]0 3 0 1
0 1[0]0 3 0 1
0 0 0 0 3[0]1
0 0 0 0 2[0]0
0 0 0 0 1[0]0
0 0 0 0 0 0 0

4[2]1 3 2 1 5
3[1]0 3 2 1 5
2[0]0 3 2 1 5
1[0]0 3 2 1 5
0 0 0 3[2]1 5
0 0 0 2[1]0 5
0 0 0 1[0]0 5
0 0 0 0 0 0[5]
0 0 0 0 0 0[4]
0 0 0 0 0 0[3]
0 0 0 0 0 0[2]
0 0 0 0 0 0[1]
0 0 0 0 0 0 0

从一个需要以某种方式下降的数字开始是一个很有吸引力的想法，因为它突然变得可以找到一个解，就像一些人声称的那样，至少和所有其他解一样好。

The next step up in complexity where this search of at least as good is still feasible is on the edge of the board. It is clear to me that there is never any strict benefit to bomb the outer edge; you're better off bombing the spot one in and getting three other spaces for free. Given this, we can say that bombing the ring one inside of the edge is at least as good as bombing the edge. Moreover, we can combine this with the intuition that bombing the right one inside of the edge is actually the only way to get edge spaces down to 0. Even more, it is trivially simple to figure out the optimal strategy (in that it is at least as good as any other strategy) to get corner numbers down to 0. We put this all together and can get much closer to a solution in the 2-D space.

根据对角子的观察，我们可以肯定地说，我们知道从任何起始棋盘到所有角子都是0的棋盘的最佳策略。这是一个这样的板的例子(我借用了上面两个线性板的数字)。我用不同的方式标记了一些空间，我会解释为什么。

0 4 2 1 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

你会注意到，最上面一行和我们之前看到的线性例子非常相似。回想一下我们之前的观察，将第一行全部降为0的最佳方法是破坏第二行(x行)。轰炸任何y行都无法清除顶部行，轰炸顶部行也没有比轰炸x行相应空间更多的好处。

我们可以从上面应用线性策略(轰炸x行上的相应空间)，只关注第一行，不关注其他任何内容。大概是这样的:

0 4 2 1 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 3 1 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 2 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 1 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 0 0 0 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

The flaw in this approach becomes very obvious in the final two bombings. It is clear, given that the only bomb sites that reduce the 4 figure in the first column in the second row are the first x and the y. The final two bombings are clearly inferior to just bombing the first x, which would have done the exact same (with regard to the first spot in the top row, which we have no other way of clearing). Since we have demonstrated that our current strategy is suboptimal, a modification in strategy is clearly needed.

在这一点上，我可以退一步，只关注一个角落。让我们考虑一下这个问题:

0 4 2 1
4 x y a
2 z . .
1 b . .

It is clear the only way to get the spaces with 4 down to zero are to bomb some combination of x, y, and z. With some acrobatics in my mind, I'm fairly sure the optimal solution is to bomb x three times and then a then b. Now it's a matter of figuring out how I reached that solution and if it reveals any intuition we can use to even solve this local problem. I notice that there's no bombing of y and z spaces. Attempting to find a corner where bombing those spaces makes sense yields a corner that looks like this:

0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .

对于这个问题，我很清楚，最优解决方案是轰炸y 5次，z 5次。让我们更进一步。

0 4 2 5 6 0 0
4 x y a . . .
2 z . . . . .
5 b . . . . .
6 . . . . . .
0 . . . . . .
0 . . . . . .

这里，最优解决方案是轰炸a和b 6次，然后x 4次。

现在它变成了一个如何将这些直觉转化为我们可以建立的原则的游戏。

希望能继续!