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

向单元格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”，我们可以使用原始问题的任何解决方案来找到最小顶点覆盖。

你的新问题，有跨行不递减的值，很容易解决。

Observe that the left column contains the highest numbers. Therefore, any optimal solution must first reduce this column to zero. Thus, we can perform a 1-D bombing run over this column, reducing every element in it to zero. We let the bombs fall on the second column so they do maximum damage. There are many posts here dealing with the 1D case, I think, so I feel safe in skipping that case. (If you want me to describe it, I can.). Because of the decreasing property, the three leftmost columns will all be reduced to zero. But, we will provably use a minimum number of bombs here because the left column must be zeroed.

现在，一旦左边的列归零，我们只要剪掉最左边的三列现在归零，然后对现在化简的矩阵重复这一步骤。这必须给我们一个最优的解决方案，因为在每个阶段我们使用可证明的最少数量的炸弹。

这可以用深度为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.

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

向单元格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”，我们可以使用原始问题的任何解决方案来找到最小顶点覆盖。

为了尽量减少炸弹的数量，我们必须最大化每个炸弹的效果。要做到这一点，每一步我们都要选择最好的目标。对于每一个点，它和它的八个邻居的总和，可以被用作轰炸这一点的效率量。这将提供接近最佳的炸弹序列。

UPD:我们还应该考虑到零的数量，因为轰炸它们效率很低。事实上，问题是最小化击中零的数量。但我们不知道每一步如何使我们更接近这个目标。我同意这个问题是np完全的。我建议用贪婪的方法，它会给出一个接近真实的答案。

评价函数，总和:

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)或这样