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

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

如果你想轰炸矩形(假设一个大矩形-还没有边缘情况) 你可以看到，只有这样才能减少空心矩形上的正方形 周长到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个正方形内的最大值就是最小值(你可能不得不分割你的轰炸来管理这一点)将是最优的，但我还没有证明。

我相信为了减少炸弹的数量，你只需要最大化伤害。 要做到这一点，需要检查具有最强力的区域。因此，您首先分析具有3x3核的场，并检查哪里的和更强。还有炸弹…一直这样做，直到场地变平。这个文件的答案是28

var oMatrix = [
[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]
]

var nBombs = 0;
do
{
    var bSpacesLeftToBomb = false;
    var nHigh = 0;
    var nCellX = 0;
    var nCellY = 0;
    for(var y = 1 ; y<oMatrix.length-1;y++) 
        for(var x = 1 ; x<oMatrix[y].length-1;x++)  
        {
            var nValue = 0;
            for(var yy = y-1;yy<=y+1;yy++)
                for(var xx = x-1;xx<=x+1;xx++)
                    nValue += oMatrix[yy][xx];

            if(nValue>nHigh)
            {
                nHigh = nValue;
                nCellX = x;
                nCellY = y; 
            }

        }
    if(nHigh>0)
    {
        nBombs++;

        for(var yy = nCellY-1;yy<=nCellY+1;yy++)
        {
            for(var xx = nCellX-1;xx<=nCellX+1;xx++)
            {
                if(oMatrix[yy][xx]<=0)
                    continue;
                oMatrix[yy][xx] = --oMatrix[yy][xx];
            }
        }
        bSpacesLeftToBomb = true;
    }
}
while(bSpacesLeftToBomb);

alert(nBombs+'bombs');

这可以用深度为O(3^(n))的树来求解。其中n是所有平方和。

首先考虑用O(9^n)树来解决问题是很简单的，只需考虑所有可能的爆炸位置。有关示例，请参阅Alfe的实现。

接下来我们意识到，我们可以从下往上轰炸，仍然得到一个最小的轰炸模式。

Start from the bottom left corner. Bomb it to oblivion with the only plays that make sense (up and to the right). Move one square to the right. While the target has a value greater than zero, consider each of the 2 plays that make sense (straight up or up and to the right), reduce the value of the target by one, and make a new branch for each possibility. Move another to the right. While the target has a value greater than zero, consider each of the 3 plays that make sense (up left, up, and up right), reduce the value of the target by one, and make a new branch for each possibility. Repeat steps 5 and 6 until the row is eliminated. Move up a row and repeat steps 1 to 7 until the puzzle is solved.

这个算法是正确的，因为

有必要在某一时刻完成每一行。 完成一行总是需要一个游戏，一个在上面，一个在下面，或者在这一行内。 选择在未清除的最低行之上的玩法总是比选择在该行之上或该行之下的玩法更好。

在实践中，这个算法通常会比它的理论最大值做得更好，因为它会定期轰炸邻居并减少搜索的大小。如果我们假设每次轰炸都会减少4个额外目标的价值，那么我们的算法将运行在O(3^(n/4))或大约O(1.3^n)。

Because this algorithm is still exponential, it would be wise to limit the depth of the search. We might limit the number of branches allowed to some number, X, and once we are this deep we force the algorithm to choose the best path it has identified so far (the one that has the minimum total board sum in one of its terminal leaves). Then our algorithm is guaranteed to run in O(3^X) time, but it is not guaranteed to get the correct answer. However, we can always increase X and test empirically if the trade off between increased computation and better answers is worthwhile.

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

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

如果你想轰炸矩形(假设一个大矩形-还没有边缘情况) 你可以看到，只有这样才能减少空心矩形上的正方形 周长到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个正方形内的最大值就是最小值(你可能不得不分割你的轰炸来管理这一点)将是最优的，但我还没有证明。

到目前为止，一些答案给出了指数时间，一些涉及动态规划。我怀疑这些是否有必要。

我的解是O(mnS)其中m和n是板子的维度，S是所有整数的和。这个想法相当野蛮:找到每次可以杀死最多的位置，并在0处终止。

对于给定的棋盘，它给出28步棋，并且在每次落子后打印出棋盘。

完整的，不言自明的代码:

import java.util.Arrays;

public class BombMinDrops {

    private static final int[][] BOARD = {{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}};
    private static final int ROWS = BOARD.length;
    private static final int COLS = BOARD[0].length;
    private static int remaining = 0;
    private static int dropCount = 0;
    static {
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                remaining = remaining + BOARD[i][j];
            }
        }
    }

    private static class Point {
        int x, y;
        int kills;

        Point(int x, int y, int kills) {
            this.x = x;
            this.y = y;
            this.kills = kills;
        }

        @Override
        public String toString() {
            return dropCount + "th drop at [" + x + ", " + y + "] , killed " + kills;
        }
    }

    private static int countPossibleKills(int x, int y) {
        int count = 0;
        for (int row = x - 1; row <= x + 1; row++) {
            for (int col = y - 1; col <= y + 1; col++) {
                try {
                    if (BOARD[row][col] > 0) count++;
                } catch (ArrayIndexOutOfBoundsException ex) {/*ignore*/}
            }
        }

        return count;
    }

    private static void drop(Point here) {
        for (int row = here.x - 1; row <= here.x + 1; row++) {
            for (int col = here.y - 1; col <= here.y + 1; col++) {
                try {
                    if (BOARD[row][col] > 0) BOARD[row][col]--;
                } catch (ArrayIndexOutOfBoundsException ex) {/*ignore*/}
            }
        }

        dropCount++;
        remaining = remaining - here.kills;
        print(here);
    }

    public static void solve() {
        while (remaining > 0) {
            Point dropWithMaxKills = new Point(-1, -1, -1);
            for (int i = 0; i < ROWS; i++) {
                for (int j = 0; j < COLS; j++) {
                    int possibleKills = countPossibleKills(i, j);
                    if (possibleKills > dropWithMaxKills.kills) {
                        dropWithMaxKills = new Point(i, j, possibleKills);
                    }
                }
            }

            drop(dropWithMaxKills);
        }

        System.out.println("Total dropped: " + dropCount);
    }

    private static void print(Point drop) {
        System.out.println(drop.toString());
        for (int[] row : BOARD) {
            System.out.println(Arrays.toString(row));
        }

        System.out.println();
    }

    public static void main(String[] args) {
        solve();
    }

}

这是另一个想法:

让我们先给黑板上的每个空格分配一个权重，计算在那里扔炸弹会减少多少数字。如果这个空间有一个非零数，它就得到一个点，如果它的相邻空间有一个非零数，它就得到一个额外的点。如果这是一个1000 * 1000的网格，我们为这100万个空间中的每一个都分配了权重。

然后根据权重对列表中的空格进行排序，并轰炸权重最高的空格。可以这么说，这是我们最大的收获。

在此之后，更新每个空间的重量是受炸弹的影响。这是你轰炸的空间，和它相邻的空间，以及它们相邻的空间。换句话说，任何空间的价值都可能因为爆炸而减少为零，或者相邻空间的价值减少为零。

然后，根据权重重新排序列表空间。由于轰炸只改变了一小部分空间的权重，因此不需要使用整个列表，只需在列表中移动这些空间。

轰炸新的最高权重空间，并重复上述步骤。

这保证了每次轰炸都能减少尽可能多的空格(基本上，它会击中尽可能少的已经为零的空格)，所以这是最优的，除非它们的权重是相同的。所以你可能需要做一些回溯跟踪，当有一个平局的顶部重量。不过，只有最高重量的领带重要，其他领带不重要，所以希望没有太多的回溯。

Edit: Mysticial's counterexample below demonstrates that in fact this isn't guaranteed to be optimal, regardless of ties in weights. In some cases reducing the weight as much as possible in a given step actually leaves the remaining bombs too spread out to achieve as high a cummulative reduction after the second step as you could have with a slightly less greedy choice in the first step. I was somewhat mislead by the notion that the results are insensitive to the order of bombings. They are insensitive to the order in that you could take any series of bombings and replay them from the start in a different order and end up with the same resulting board. But it doesn't follow from that that you can consider each bombing independently. Or, at least, each bombing must be considered in a way that takes into account how well it sets up the board for subsequent bombings.