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

评价函数，总和:

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

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

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.

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

这里似乎有一个非二部匹配子结构。考虑下面的例子:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

这种情况下的最佳解决方案的大小为5，因为这是9-cycle的边的最小顶点覆盖的大小。

这个例子，特别地，表明了一些人发布的线性规划松弛法是不精确的，不管用，还有其他一些不好的东西。我很确定我可以减少“用尽可能少的边覆盖我的平面立方图的顶点”来解决你的问题，这让我怀疑任何贪婪/爬坡的解决方案是否有效。

在最坏的情况下，我找不到在多项式时间内解出来的方法。可能有一个非常聪明的二进制搜索和dp解决方案，但我没有看到。

编辑:我看到这个比赛(http://deadline24.pl)是语言无关的;他们给你一堆输入文件，你给他们输出。所以你不需要在最坏情况下多项式时间内运行的东西。特别是，您可以查看输入!

There are a bunch of small cases in the input. Then there's a 10x1000 case, a 100x100 case, and a 1000x1000 case. The three large cases are all very well-behaved. Horizontally adjacent entries typically have the same value. On a relatively beefy machine, I'm able to solve all of the cases by brute-forcing using CPLEX in just a couple of minutes. I got lucky on the 1000x1000; the LP relaxation happens to have an integral optimal solution. My solutions agree with the .ans files provided in the test data bundle.

我敢打赌你可以用比我更直接的方式使用输入的结构，如果你看了它;看起来你只需要砍掉第一行，或者两行，或者三行直到你什么都不剩。(看起来，在1000x1000中，所有的行都是不增加的?我猜这就是你的“B部分”的来源吧?)

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

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

如果你想要绝对最优解来清理棋盘，你将不得不使用经典的回溯，但如果矩阵非常大，它将需要很长时间才能找到最佳解，如果你想要一个“可能的”最优解，你可以使用贪婪算法，如果你需要帮助写算法，我可以帮助你

现在想想，这是最好的办法。在那里制作另一个矩阵，存储通过投掷炸弹而移除的点，然后选择点数最多的单元格，并在那里投掷炸弹更新点数矩阵，然后继续。例子:

2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3))
1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4))
1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2))

对于每个相邻的高于0的单元格，单元格值+1