algorithm - 炸弹投放算法

Question

我有一个n x m由非负整数组成的矩阵。例如：

“投下炸弹”将目标单元及其所有八个相邻单元的数量减少一，最小为零。

x x x 
x X x
x x x

什么算法可以确定将所有单元格减少到零所需的最小炸弹数量？

B选项（由于我不是一个细心的读者）

实际上问题的第一个版本不是我正在寻找答案的那个。我没有仔细阅读整个任务，还有额外的限制，让我们说：

简单的问题呢，当行中的序列必须不增加时：

8 7 6 6 5是可能的输入序列

7 8 5 5 2不可能，因为 7 -> 8 按顺序增长。

也许为“更简单”的案例找到答案将有助于为更难的案例找到解决方案。

PS：我相信当我们有几个相同的情况需要最少的炸弹来清除上线时，我们会选择在行的“左侧”使用最多的炸弹。还有任何可能是正确的证据吗？

score 38 · Accepted Answer

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

解释有两部分，算法，以及算法提供最佳解决方案的原因。如果没有第二个，第一个就没有意义，所以我将从为什么开始。

如果您考虑轰炸矩形（假设是一个大矩形 - 还没有边缘情况），您可以看到将周边正方形的空心矩形减少到 0 的唯一方法是轰炸周边或轰炸空心矩形正方形就在外围。我将把外围层称为第 1 层，将其内部的矩形称为第 2 层。

一个重要的见解是没有点轰炸第 1 层，因为这样做得到的“爆炸半径”总是包含在第 2 层的另一个正方形的爆炸半径内。您应该能够轻松地说服自己这一点。

因此，我们可以将问题简化为找到一个最佳方法来轰炸周界，然后我们可以重复这个过程，直到所有方格都为 0。

但是当然，如果有可能以一种不太理想的方式轰炸周边，这并不总是能找到最佳解决方案，但是通过使用 X 个额外的炸弹，通过 >X 个炸弹减少内层的问题变得更简单。所以，如果我们调用许可者第一层，如果我们在第二层的某个地方（就在第一层内部）放置一个额外的 X 炸弹，我们可以减少后来轰炸第二层的工作量超过 X 吗？换句话说，我们必须证明我们可以贪婪地减少外围。

但是，我们确实知道我们可以贪婪。因为在将第 2 层减少到 0 层时，第 2 层中的任何炸弹都不会比第 3 层中战略性放置的炸弹更有效。出于与以前相同的原因 - 我们总是可以在第 3 层中放置一颗炸弹，它会影响每个方格放置在第 2 层的炸弹可以达到第 2 层。所以，贪婪永远不会伤害我们（在这种贪婪的意义上）。

所以，我们所要做的就是找到最佳方法，通过轰炸下一个内层将permiter减少到0。

先把拐角轰到0我们是不会受伤的，因为只有内层的拐角才能到达，所以我们真的别无选择（而且，任何能到达拐角的外围炸弹的爆炸半径都包含在内层角的爆炸半径）。

一旦我们这样做了，与 0 角相邻的周边方格只能从内层到达 2 个方格：

0       A       B

C       X       Y

D       Z

此时，周界实际上是一个封闭的 1 维循环，因为任何炸弹都会减少 3 个相邻的方格。除了角落附近的一些奇怪之处 - X 可以“击中” A、B、C 和 D。

现在我们不能使用任何爆炸半径技巧 - 每个方格的情况都是对称的，除了奇怪的角落，即使没有爆炸半径也是另一个的子集。请注意，如果这是一条线（正如恐慌上校所讨论的）而不是一个闭环，那么解决方案是微不足道的。端点必须减少到 0，并且炸毁与端点相邻的点永远不会对您造成伤害，因为爆炸半径是超集。将端点设为 0 后，您仍然有一个新端点，因此重复（直到该行全为 0）。

因此，如果我们可以将层中的单个正方形最佳地减少到 0，我们就有了一个算法（因为我们已经切断了循环，现在有一条带端点的直线）。我相信在具有最低值的正方形附近进行轰炸（给您 2 个选项），以便在该最小值的 2 个正方形内的最大值是可能的最小值（您可能必须拆分轰炸来管理这个）将是最佳的，但我（还没有？）有证据。

score 26 · Accepted Answer

Pólya says "If you can't solve a problem, then there is an easier problem you can solve: find it."

The obvious simpler problem is the 1-dimensional problem (when the grid is a single row). Let's start with the simplest algorithm - greedily bombing the biggest target. When does this go wrong?

Given 1 1 1, the greedy algorithm is indifferent to which cell it bombs first. Of course, the centre cell is better - it zeros all three cells at once. This suggests a new algorithm A, "bomb to minimise the sum remaining". When does this algorithm go wrong?

Given 1 1 2 1 1, algorithm A is indifferent between bombing the 2nd, 3rd or 4th cells. But bombing the 2nd cell to leave 0 0 1 1 1 is better than bombing the 3rd cell to leave 1 0 1 0 1. How to fix that? The problem with bombing the 3rd cell is that it leaves us work to the left and work to the right which must be done separately.

How about "bomb to minimise the sum remaining, but maximise the minimum to the left (of where we bombed) plus the minimum to the right". Call this algorithm B. When does this algorithm go wrong?

Edit: After reading the comments, I agree a much more interesting problem would be the one dimensional problem changed so that the ends join up. Would love to see any progress on that.

score 12 · Accepted Answer

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

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

0 4 2 1 3 0 1

不知何故，您知道您需要在该4地点或附近轰炸 4 次才能将其降至 0。由于该地点左侧的数字较低，因此轰炸0或4过度轰炸. 没有任何好处2。事实上，我相信（但缺乏严格的证据）轰炸2直到4点下降到 0 至少与任何其他将点下降到 0 的策略一样好。4一个人可以在策略中从左到右进行像这样：

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

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

在复杂性的下一步中，这种至少同样好的搜索仍然可行是在棋盘的边缘。我很清楚，轰炸外缘从来没有任何严格的好处。你最好轰炸一个地点并免费获得另外三个空间。鉴于此，我们可以说在边缘内部轰炸第一环至少与轰炸边缘一样好。此外，我们可以将此与直觉相结合，即在边缘内部轰炸正确的边缘实际上是使边缘空间降至 0 的唯一方法。更重要的是，找出最优策略非常简单（因为它在至少与任何其他策略一样好）将角数降至 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

这种方法的缺陷在最后两次轰炸中变得非常明显。很明显，考虑到减少4第二行第一列中数字的唯一炸弹站点是第一个x和y. 最后的两次轰炸显然不如只轰炸第一次x，后者的效果完全一样（关于顶行的第一个位置，我们没有其他方法可以清除）。由于我们已经证明我们当前的策略是次优的，因此显然需要对策略进行修改。

在这一点上，我可以在复杂性上退后一步，只关注一个角落。让我们考虑这个：

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

很明显，使空格4降为零的唯一方法是轰炸x、y和的某种组合z。考虑到一些杂技，我相当确定最佳解决方案是轰炸x三下a然后b。现在的问题是弄清楚我是如何达到这个解决方案的，以及它是否揭示了我们甚至可以用来解决这个本地问题的任何直觉。我注意到没有轰炸y和z空间。试图找到一个可以轰炸这些空间的角落会产生一个看起来像这样的角落：

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

对于这个，我很清楚，最佳解决方案是轰炸y5 次和z5 次。让我们更进一步。

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

在这里，感觉同样直观，最佳解决方案是轰炸6 次，然后a4次。bx

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

希望能继续！

score 11 · Accepted Answer

对于更新的问题，一个简单的贪心算法给出了最佳结果。

向单元格 A[1,1] 投放 A[0,0] 炸弹，然后向单元格 A[2,1] 投放 A[1,0] 炸弹，并继续向下进行此过程。要清理左下角，请将 max(A[N-1,0], A[N-2,0], A[N-3,0]) 炸弹放到单元格 A[N-2,1] 中。这将完全清理前 3 列。

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

不幸的是，这无助于找到原始问题的解决方案。

“更大”的问题（没有“非增减”约束）可能被证明是 NP 难的。这是一个证明的草图。

假设我们有一个度数不超过 3 的平面图。让我们找到该图的最小顶点覆盖。根据维基百科的文章，对于度数高达 3 的平面图，这个问题是 NP-hard。这可以通过 Planar 3SAT 的归约来证明。平面 3SAT 的硬度 - 由 3SAT 降低。这两个证明都在教授最近的“算法下界”讲座中提出。Erik Demaine（第 7 和第 9 课）。

如果我们分割原始图的一些边（图上的左图），每条边都有偶数个附加节点，则结果图（图上的右图）应该具有与原始顶点完全相同的最小顶点覆盖。这种转换允许将图形顶点与网格上的任意位置对齐。

在此处输入图像描述

如果我们只将图形顶点放置到偶数行和列（以这样一种方式，没有两条边与一个顶点入射形成锐角），则在有边的地方插入“1”，并在其他网格位置插入“零”，我们可以对原始问题使用任何解决方案来找到最小顶点覆盖。

score 9 · Accepted Answer

这是部分答案，我试图找到可能是炸弹数量的下限和上限。

在 3x3 和更小的板中，解决方案通常是最大编号的单元。

在大于 4x4 的棋盘中，第一个明显的下限是角的总和：

*2* 3  7 *1*
 1  5  6  2
 2  1  3  2
*6* 9  6 *4*

不管你怎么安排炸弹，用少于 2+1+6+4=13 个炸弹是不可能清除这个 4x4 棋盘的。

在其他答案中已经提到，将炸弹放在第二个角落以消除角落永远不会比将炸弹放在角落本身更糟糕，所以给定棋盘：

*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*

我们可以通过在倒数第二个角落放置炸弹来将角落归零，从而得到一个新的棋盘：

 0  1  1  6  0
 0  3  0  5  1
 2  1  1  1  0
 2  1  2  4  1
 0  0  0  0  0
 0  0  0  0  0
 0  3  0  2  0

到目前为止，一切都很好。我们需要 13 颗炸弹来清理角落。

现在观察下面标记的数字 6、4、3 和 2：

 0  1  1 *6* 0
 0  3  0  5  1
 2  1  1  1  0
*2* 1  2 *4* 1
 0  0  0  0  0
 0  0  0  0  0
 0 *3* 0  2  0

没有办法用一颗炸弹轰炸任何两个牢房，所以最小炸弹增加了 6+4+3+2，所以加上我们用来清除角落的炸弹数量，我们得到了最小炸弹这张地图所需的炸弹数量已变为 28 颗。少于 28 颗炸弹是不可能通关这张地图的，这是这张地图的下限。

您可以使用贪心算法来建立一个上限。其他答案表明，贪心算法会产生使用 28 个炸弹的解决方案。由于我们之前已经证明，没有最优解不能少于 28 颗炸弹，因此 28 颗炸弹确实是最优解。

当贪婪和我上面提到的找到最小界限的方法没有收敛时，我想你必须回去检查所有组合。

寻找下限的算法如下：

选择一个编号最大的元素，将其命名为 P。
将距离 P 和 P 本身两步的所有单元格标记为不可拾取。
将 P 添加到minimums列表中。
重复步骤 1，直到所有单元格都不可拾取。
对列表求和minimums以获得下限。

score 9 · Accepted Answer

您可以将此问题表示为整数规划问题。（这只是解决此问题的可能解决方案之一）

有要点：

a b c d
e f g h
i j k l
m n o p

一个人可以写出 16 个方程，例如，对于点 f 成立

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki

最小化所有索引和整数解的总和。

解决方案当然是这些指标的总和。

这可以通过将所有 xi 设置在边界 0 上来进一步简化，因此在此示例中您最终会得到 4+1 方程。

问题是没有解决此类问题的简单算法。我不是这方面的专家，但是解决这个问题，因为线性规划是 NP 困难的。

score 9 · Accepted Answer

这将是一种贪婪的方法：

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

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

编辑：

我在上面发布的贪婪方法虽然有效，但很可能不会为我们提供最佳解决方案。所以我认为应该在其中添加一些 DP 元素。

我认为我们可以同意，在任何时间点，必须瞄准具有最高“分数”的位置之一（score[i][j] = 如果 (i,j) 被轰炸，则总扣分）。从这个假设开始，这是新的方法：

NumOfBombs(M)：（返回所需的最小轰炸次数）

给定一个 n X m 阶的矩阵 M。如果 M 的所有元素都为零，则返回 0。
计算“分数”矩阵 M。

设 k 个不同的位置 P1,P2,...Pk (1 <= k <= n*m) 是 M 中得分最高的位置。
返回 (1 + min( NumOfBombs(M1), NumOfBombs(M2), ..., NumOfBombs(Mk) ) )

其中 M1,M2,...,Mk 是我们分别轰炸位置 P1,P2,...,Pk 时的结果矩阵。

此外，如果我们想要除此之外的位置顺序，我们必须跟踪“min”的结果。

score 8 · Accepted Answer

您的新问题（跨行的值不递减）很容易解决。

观察左列包含最高的数字。因此，任何最优解都必须首先将该列减少为零。因此，我们可以对该列执行一维轰炸，将其中的每个元素减少为零。我们让炸弹落在第二列，这样它们就会造成最大的伤害。我认为这里有很多关于一维案例的帖子，所以我觉得跳过那个案例是安全的。（如果你想让我描述它，我可以。）。由于递减属性，最左边的三列将全部归零。但是，我们将在这里证明使用最少数量的炸弹，因为左列必须归零。

现在，一旦左列归零，我们只需剪掉现在归零的最左边的三列，并使用现在减少的矩阵重复。这必须为我们提供最佳解决方案，因为在每个阶段我们使用可证明的最少数量的炸弹。

score 4 · Accepted Answer

使用分支定界的 Mathematica 整数线性规划

正如已经提到的，这个问题可以使用整数线性规划（即NP-Hard）来解决。Mathematica 已经内置了 ILP。"To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method."[参见Mathematica 中的约束优化教程..]

我编写了以下使用 Mathematica 的 ILP 库的代码。它出奇的快。

solveMatrixBombProblem[problem_, r_, c_] := 
 Module[{}, 
  bombEffect[x_, y_, m_, n_] := 
   Table[If[(i == x || i == x - 1 || i == x + 1) && (j == y || 
        j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}];
  bombMatrix[m_, n_] := 
   Transpose[
    Table[Table[
      Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m, 
        n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0, 
       m*n - 1}], {i, 0, m*n - 1}]];
  X := x /@ Range[c*r];
  sol = Minimize[{Total[X], 
     And @@ Thread[bombMatrix[r, c].X >= problem] && 
      And @@ Thread[X >= 0] && Total[X] <= 10^100 && 
      Element[X, Integers]}, X];
  Print["Minimum required bombs = ", sol[[1]]];
  Print["A possible solution = ", 
   MatrixForm[
    Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0, 
      c - 1}]]];]

对于问题中提供的示例：

solveMatrixBombProblem[{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}, 7, 5]

输出

在此处输入图像描述

对于任何使用贪心算法阅读本文的人

在以下 10x10 问题上尝试您的代码：

5   20  7   1   9   8   19  16  11  3  
17  8   15  17  12  4   5   16  8   18  
4   19  12  11  9   7   4   15  14  6  
17  20  4   9   19  8   17  2   10  8  
3   9   10  13  8   9   12  12  6   18  
16  16  2   10  7   12  17  11  4   15  
11  1   15  1   5   11  3   12  8   3  
7   11  16  19  17  11  20  2   5   19  
5   18  2   17  7   14  19  11  1   6  
13  20  8   4   15  10  19  5   11  12

这里是逗号分隔的：

5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12

对于这个问题，我的解决方案包含208 个炸弹。这是一个可能的解决方案（我能够在大约 12 秒内解决这个问题）。

在此处输入图像描述

作为测试 Mathematica 产生的结果的一种方法，看看你的贪心算法是否可以做得更好。

score 3 · Accepted Answer

似乎线性规划方法在这里非常有用。

令P _{m xn}是具有位置值的矩阵：

职位矩阵

现在让我们定义一个炸弹矩阵 B(x, y) _mxn，其中1 ≤ x ≤ m , 1 ≤ y ≤ n如下

炸弹矩阵

以这样的方式

炸弹矩阵中的位置值

例如：

乙(3, 3)

所以我们正在寻找一个矩阵B _{m xn} = [ b _ij ]

可以定义为炸弹矩阵的总和：

（q _ij将是我们将在位置p _ij投放的炸弹数量）
p _ij - b _ij ≤ 0 （为了更简洁，让我们将其称为P - B ≤ 0）

此外，B应该最小化 sum 炸弹数量的总和。

我们也可以将B写成前面的丑陋矩阵：

B 作为数量和的矩阵

并且由于P - B ≤ 0（这意味着P ≤ B）我们有以下漂亮的线性不等式系统：

投弹数与位置数值的关系

被q _{mn x 1}定义为

数量向量

p _{mn x 1}定义为

P 的值作为向量分布

我们可以说我们有一个系统是S _{mn x mn}矩阵要反转来解决系统。我自己没有扩展它，但我相信在代码中应该很容易做到。

现在，我们有一个最小问题，可以表示为

我们必须解决的系统

我相信用单纯形算法之类的东西来解决它很容易，几乎是微不足道的（有一个关于它的相当酷的文档）。然而，我几乎不知道线性规划（我将在 Coursera 上学习关于它的课程，但它只是在将来......），我在试图理解它时有些头疼，我还有一份巨大的自由职业要完成，所以我就在这里放弃吧。可能是我在某个时候做错了什么，或者它不能走得更远，但我相信这条路最终会导致解决方案。无论如何，我很期待你的反馈。

（特别感谢这个从 LaTeX 表达式创建图片的神奇网站）

score 3 · Accepted Answer

这会在这个位置“迷宫”中搜索最短路径（一系列轰炸）。不，我无法证明没有更快的算法，抱歉。

#!/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))

score 3 · Accepted Answer

无需将问题转换为线性子问题。

取而代之的是使用简单的贪婪启发式，即从最大的一个开始轰炸角落。

在给定的示例中，有四个角，{ 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 个新角，{ 2, 1 } 在第 4 行。我们轰炸那些，另外 3 次轰炸。我们现在已将矩阵缩减为 4 x 4。有一个角落，左上角。我们轰炸那个。现在我们剩下 2 个角，{ 5, 3 }。由于 5 是最大的角落，我们首先轰炸 5 个，然后最后轰炸另一个角落的 3 个。总数为 13+3+3+1+5+3 = 28。

score 3 · Accepted Answer

这个贪婪的解决方案~~似乎是正确的~~：

正如评论中指出的那样，它会在 2D 中失败。但也许你可以改进它。

对于 1D：
如果至少有 2 个数字，则无需向最左边的数字射击，因为向第二个数字射击并不差。所以射击到第二个，而第一个不是 0，因为你必须这样做。移动到下一个单元格。不要忘记最后一个单元格。

C++ 代码：

void bombs(vector<int>& v, int i, int n){
    ans += n;
    v[i] -= n;
    if(i > 0)
        v[i - 1] -= n;
    if(i + 1< v.size())
        v[i + 1] -= n;
}

void solve(vector<int> v){
    int n = v.size();
    for(int i = 0; i < n;++i){
        if(i != n - 1){
            bombs(v, i + 1, v[i]);
        }
        else
            bombs(v, i, v[i])
    }
}

所以对于 2D：
同样：你不需要在第一行拍摄（如果有第二行）。于是拍第二张。解决第一行的一维任务。（因为您需要将其设为空）。下去。不要忘记最后一行。

score 2 · Accepted Answer

这是一个概括角落的良好特性的解决方案。

假设我们可以为给定字段找到一个完美的下降点，即减少其中值的最佳方法。然后要找到要投下的最小炸弹数量，算法的初稿可能是（代码是从 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)。它也可能减少其他单元格中的值。
一个下降点a比一个下降点b好，如果它减少了b减少的单元格的适当超集中的值。(x, y)(x, y)
如果没有其他更好的落点，则落点是最大的。
如果它们减少同一组单元格，则两个下降点(x, y)是等效的。
如果的落点等于的所有最大落点，则它(x, y)是完美(x, y)的。

如果有一个完美的投掷点(x, y)，你不能(x, y)比在其中一个完美的投掷点投掷炸弹更有效地减少的值(x, y)。

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

这里有几个例子：

(0, 0)单元格（从零开始的索引）的完美下降点是(1, 1). 的所有其他下降点(1, 1)，即(0, 0)、(0, 1)和(1, 0)，减少的单元格更少。

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

单元格的完美下降点(2, 2)是(3, 1)：它减少中的值(2, 2)和中的值(4, 0)。所有其他下降点(2, 2)都不是最大的，因为它们减少了一个单元格。的完美落点(2, 2)也是的完美落点(4, 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, 1)和(1, 2)。选择其中一个，然后计算最小值会导致以下结果：

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

score 2 · Accepted Answer

我相信要尽量减少炸弹的数量，你只需要最大限度地增加伤害..为此需要检查具有最强力量的区域..所以你首先用 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');

score 2 · Accepted Answer

这是另一个想法：

让我们首先为板上的每个空间分配一个权重，以了解通过在该处投掷炸弹会减少多少个数字。因此，如果空间有一个非零数，它会得到一个点，如果与它相邻的任何空间有一个非零数，它就会得到一个额外的点。因此，如果有一个 1000×1000 的网格，我们会为 100 万个空间中的每一个分配一个权重。

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

之后，更新每个重量受炸弹影响的空间的重量。这将是您轰炸的空间，以及与其紧邻的任何空间，以及与其紧邻的任何空间。换句话说，任何可能通过轰炸使其价值减少到零的空间，或者相邻空间的价值减少到零。

然后，按权重对列表空间进行重新排序。由于只有一小部分空间的重量因轰炸而改变，因此您无需使用整个列表，只需在列表中移动这些空间即可。

轰炸新的最高重量空间，并重复该过程。

这保证了每次轰炸都会减少尽可能多的空间（基本上，它会尽可能少地击中已经为零的空间），所以这将是最佳的，除了它们可以是权重关系。因此，当最高重量存在平局时，您可能需要进行一些回溯。不过，只有最高重量的领带很重要，其他的领带无关紧要，所以希望它不会有太多的回溯。

编辑： 下面 Mysticial 的反例表明，实际上这并不能保证是最佳的，无论权重如何。在某些情况下，在给定的步骤中尽可能地减少重量实际上会使剩余的炸弹过于分散，无法在第二步之后实现尽可能高的累积减少，因为第一步中的贪婪选择稍微少一些。我被认为结果对轰炸顺序不敏感的概念有些误导。他们是对顺序不敏感，因为您可以进行任何一系列的轰炸并以不同的顺序从头开始重播它们，最终得到相同的结果板。但这并不意味着您可以独立考虑每次轰炸。或者，至少，每次轰炸都必须考虑到它为随后的轰炸设置董事会的程度。

score 2 · Accepted Answer

为了尽量减少炸弹的数量，我们必须最大化每颗炸弹的效果。为了实现这一目标，我们必须在每一步中选择最佳目标。对于每个点求和它和它的八个邻居 - 可以用作轰炸该点的效率量。这将提供接近最佳的炸弹序列。

UPD：我们还应该考虑零的数量，因为轰炸它们效率低下。事实上，问题是尽量减少命中零的数量。但我们不知道任何一步如何使我们更接近这一目标。我同意这个问题是 NP 完全的。我建议采用贪婪的方法，这将给出接近真实的答案。

score 1 · Accepted Answer

如果您想要绝对最优解来清理棋盘，则必须使用经典回溯，但如果矩阵非常大，则需要很长时间才能找到最佳解，如果您想要“可能的”最优解，则可以使用贪心算法，如果您在编写算法时需要帮助，我可以帮助您

想想这是最好的方法。在那里制作另一个矩阵，您通过在那里放置炸弹来存储您删除的点，然后选择具有最大点的单元格并将炸弹放在那里更新点矩阵并继续。例子：

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

score 1 · Accepted Answer

Well, suppose we number the board positions 1, 2, ..., n x m. Any sequence of bomb drops can be represented by a sequence of numbers in this set, where numbers can repeat. However, the effect on the board is the same regardless of what order you drop the bombs in, so really any choice of bomb drops can be represented as a list of n x m numbers, where the first number represents the number of bombs dropped on position 1, the second number represents the number of bombs dropped on position 2, etc. Let's call this list of n x m numbers the "key".

You could try first calculating all board states resulting from 1 bomb drop, then use these to calculate all board states resulting from 2 bomb drops, etc until you get all zeros. But at each step you would cache the states using the key I defined above, so you can use these results in calculating the next step (a "dynamic programming" approach).

But depending on the size of n, m, and the numbers in the grid, the memory requirements of this approach might be excessive. You can throw away all the results for N bomb drops once you've calculated all the results for N + 1, so there's some savings there. And of course you could not cache anything at the cost of having it take a lot longer -- the dynamic programming approach trades memory for speed.

score 1 · Accepted Answer

这是我的解决方案..由于我没有时间，所以我不会用代码写出来，但我相信这应该每次都会产生最佳的移动次数 - 尽管我不确定它在寻找时的效率如何要轰炸的点。

首先，正如@Luka Rahne 在其中一条评论中所说，你轰炸的顺序并不重要——只有组合。

其次，正如许多其他人所说，从角落轰炸对角线 1 是最佳的，因为它接触的点比角落多。

这为我的算法版本奠定了基础：我们可以首先或最后轰炸“从角落开始的一关”，这并不重要（理论上）我们先轰炸那些，因为它使以后的决策更容易（在实践中）我们轰炸影响最多点的点，同时轰炸那些角落。

让我们将Points Of Resistance定义为棋盘中具有最多不可轰炸点+周围0 最多的点

不可轰炸点可以定义为我们当前正在查看的棋盘范围内不存在的点。

我还将定义 4 个边界来处理我们的范围：Top=0、Left=0、Bottom=k、right=j。（开始的值）

最后，我将最佳炸弹定义为投在与阻力点相邻的点上并接触（1）最高阻力点和（2）尽可能多的点的炸弹。

关于方法——很明显我们是从外向内工作。我们将能够同时与 4 个“轰炸机”一起工作。

第一个阻力点显然是我们的角落。“越界”点是不可轰炸的（每个角有 5 个超出范围的点）。所以我们首先从角上对角地轰炸点。

算法：

找到 4 个最佳炸弹点。
如果一个炸弹点正在轰炸一个接触 2 个边界（即一个角）的阻力点，则轰炸该点为 0。否则，轰炸每个点，直到接触最佳炸弹点的阻力点之一为 0。
对于每个界限： if(sum(bound)==0) 提前界限

重复直到 TOP=BOTTOM 和 LEFT=RIGHT

稍后我将尝试编写实际代码

score 1 · Accepted Answer

评价函数，总和：

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));
    }
}

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

..但是考虑到这个问题，我认为主要问题之一是在某个时候在零中间得到被遗弃的数字，所以我会采取另一种方法..将最小值控制为零，然后尝试尽可能转义零，这导致最小现有值的一般最小化左右

score 1 · Accepted Answer

永远不要轰炸边界（除非正方形没有非边界邻居）
零角。
零角，将角的值下降一平方对角线（唯一的非边界邻居）
这将创建新的角落。前往 2

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

在 OP 的示例中：将 2（作为 1+1 或 2）放在 5 以外的任何东西上不会导致击中任何放在 5 上会击中的方格。所以我们必须将 2 放在 5 上（以及 6 放在左下方 1 ...）

在此之后，只有一种方法可以清除（在左上角）原来的 1（现在为 0），即在 B3 上删除 0（类似于符号的 Excel）。等等。

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

只考虑清除那些有意清除的，清除 0 值角不花费任何成本并简化思考。

因为以这种方式投下的所有炸弹都必须投下，这会导致空地，这是最佳解决方案。

经过良好的睡眠，我意识到这不是真的。考虑

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

score 1 · Accepted Answer

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

首先考虑用 O(9^n) 的树来解决问题是微不足道的，只需考虑所有可能的轰炸位置。有关示例，请参见Alfe 的实现。

接下来意识到我们可以从下到上进行轰炸，并且仍然获得最小轰炸模式。

从左下角开始。
用唯一有意义的戏剧（向上和向右）将其轰炸到遗忘。
向右移动一格。
虽然目标的值大于零，但考虑两个有意义的玩法（直接向上或向上和向右），将目标的值减少 1，并为每种可能性创建一个新分支。
向右移动另一个。
虽然目标的值大于零，但考虑三个有意义的游戏（左上、上和右上）中的每一个，将目标的值减一，并为每种可能性创建一个新分支。
重复步骤 5 和 6，直到该行被消除。
向上移动一行并重复步骤 1 到 7，直到拼图解决。

这个算法是正确的，因为

有必要在某个时候完成每一行。
完成一行总是需要在该行的上方、下方或在该行内进行游戏。
选择最低未清除行上方的游戏总是与该行或该行下方的游戏一样好或更好。

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

因为这个算法仍然是指数的，所以限制搜索的深度是明智的。我们可能会将允许的分支数量限制为某个数字 X，一旦我们达到这个深度，我们就会强制算法选择它迄今为止识别的最佳路径（在它的一个终端叶中具有最小总棋盘总和的路径））。那么我们的算法保证在 O(3^X) 时间内运行，但不能保证得到正确答案。但是，如果增加计算量和更好的答案之间的权衡是值得的，我们总是可以增加 X 并进行经验测试。

score 1 · Accepted Answer

这里似乎有一个非二分匹配子结构。考虑以下实例：

这种情况的最佳解决方案的大小为 5，因为这是 9 循环的顶点对其边缘的最小覆盖的大小。

特别是这个案例表明，一些人发布的线性规划松弛并不准确，不起作用，以及所有其他不好的事情。我很确定我可以减少“用尽可能少的边覆盖我的平面三次图的顶点”来解决您的问题，这让我怀疑任何贪婪/爬山解决方案是否会起作用。

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

编辑：我看到比赛（http://deadline24.pl）与语言无关；他们向您发送一堆输入文件，然后您向他们发送输出。所以你不需要在最坏情况多项式时间内运行的东西。特别是，您可以查看输入！

输入中有一堆小案例。然后有一个 10x1000 的情况，一个 100x100 的情况和一个 1000x1000 的情况。三个大案子都非常乖巧。水平相邻的条目通常具有相同的值。在一台相对强大的机器上，我能够在几分钟内通过使用 CPLEX 暴力破解来解决所有问题。我在 1000x1000 上很幸运；LP 松弛恰好有一个积分最优解。我的解决方案与.ans测试数据包中提供的文件一致。

我敢打赌，如果您看一下，您可以以比我更直接的方式使用输入的结构；似乎您可以反复削减第一行或两行或三行，直到一无所有。（看起来，在 1000x1000 中，所有行都没有增加？我猜这就是你的“B 部分”的来源？）

score 1 · Accepted Answer

您可以使用状态空间规划。例如，使用 A*（或其变体之一）加上f = g + h这样的启发式：

g：到目前为止投下的炸弹数量
h：将网格的所有值相加除以 9（这是最好的结果，这意味着我们有一个可接受的启发式）

score 1 · Accepted Answer

如果不使用我最好的启发式计算轰炸活动，我想不出一种方法来计算实际数字，并希望我能得到一个合理的结果。

所以我的方法是计算每个单元格的轰炸效率指标，轰炸具有最高值的单元格，....迭代过程，直到我把所有东西都弄平。一些人主张使用简单的潜在损坏（即从 0 到 9 的分数）作为衡量标准，但由于敲击高价值单元而不使用损坏重叠而达不到要求。我会计算cell value - sum of all neighbouring cells，将任何正数重置为 0 并使用任何负数的绝对值。直观地说，这个指标应该做出一个选择，以帮助最大化对高计数细胞的损伤重叠，而不是直接冲击那些细胞。

下面的代码在 28 枚炸弹中达到了对测试场的完全破坏（请注意，使用潜在损坏作为度量会产生 31！）。

using System;
using System.Collections.Generic;
using System.Linq;

namespace StackOverflow
{
  internal class Program
  {
    // store the battle field as flat array + dimensions
    private static int _width = 5;
    private static int _length = 7;
    private static int[] _field = new int[] {
        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
    };
    // this will store the devastation metric
    private static int[] _metric;

    // do the work
    private static void Main(string[] args)
    {
        int count = 0;

        while (_field.Sum() > 0)
        {
            Console.Out.WriteLine("Round {0}:", ++count);
            GetBlastPotential();
            int cell_to_bomb = FindBestBombingSite();
            PrintField(cell_to_bomb);
            Bomb(cell_to_bomb);
        }
        Console.Out.WriteLine("Done in {0} rounds", count);
    } 

    // convert 2D position to 1D index
    private static int Get1DCoord(int x, int y)
    {
        if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
        else
        {
            return (y * _width) + x;
        }
    }

    // Convert 1D index to 2D position
    private static void Get2DCoord(int n, out int x, out int y)
    {
        if ((n < 0) || (n >= _field.Length))
        {
            x = -1;
            y = -1;
        }
        else
        {
            x = n % _width;
            y = n / _width;
        }
    }

    // Compute a list of 1D indices for a cell neighbours
    private static List<int> GetNeighbours(int cell)
    {
        List<int> neighbours = new List<int>();
        int x, y;
        Get2DCoord(cell, out x, out y);
        if ((x >= 0) && (y >= 0))
        {
            List<int> tmp = new List<int>();
            tmp.Add(Get1DCoord(x - 1, y - 1));
            tmp.Add(Get1DCoord(x - 1, y));
            tmp.Add(Get1DCoord(x - 1, y + 1));
            tmp.Add(Get1DCoord(x, y - 1));
            tmp.Add(Get1DCoord(x, y + 1));
            tmp.Add(Get1DCoord(x + 1, y - 1));
            tmp.Add(Get1DCoord(x + 1, y));
            tmp.Add(Get1DCoord(x + 1, y + 1));

            // eliminate invalid coords - i.e. stuff past the edges
            foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
        }
        return neighbours;
    }

    // Compute the devastation metric for each cell
    // Represent the Value of the cell minus the sum of all its neighbours
    private static void GetBlastPotential()
    {
        _metric = new int[_field.Length];
        for (int i = 0; i < _field.Length; i++)
        {
            _metric[i] = _field[i];
            List<int> neighbours = GetNeighbours(i);
            if (neighbours != null)
            {
                foreach (int j in neighbours) _metric[i] -= _field[j];
            }
        }
        for (int i = 0; i < _metric.Length; i++)
        {
            _metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
        }
    }

    //// Compute the simple expected damage a bomb would score
    //private static void GetBlastPotential()
    //{
    //    _metric = new int[_field.Length];
    //    for (int i = 0; i < _field.Length; i++)
    //    {
    //        _metric[i] = (_field[i] > 0) ? 1 : 0;
    //        List<int> neighbours = GetNeighbours(i);
    //        if (neighbours != null)
    //        {
    //            foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
    //        }
    //    }            
    //}

    // Update the battle field upon dropping a bomb
    private static void Bomb(int cell)
    {
        List<int> neighbours = GetNeighbours(cell);
        foreach (int i in neighbours)
        {
            if (_field[i] > 0) _field[i]--;
        }
    }

    // Find the best bombing site - just return index of local maxima
    private static int FindBestBombingSite()
    {
        int max_idx = 0;
        int max_val = int.MinValue;
        for (int i = 0; i < _metric.Length; i++)
        {
            if (_metric[i] > max_val)
            {
                max_val = _metric[i];
                max_idx = i;
            }
        }
        return max_idx;
    }

    // Display the battle field on the console
    private static void PrintField(int cell)
    {
        for (int x = 0; x < _width; x++)
        {
            for (int y = 0; y < _length; y++)
            {
                int c = Get1DCoord(x, y);
                if (c == cell)
                    Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4));
                else
                    Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4));
            }
            Console.Out.Write(" || ");
            for (int y = 0; y < _length; y++)
            {
                int c = Get1DCoord(x, y);
                if (c == cell)
                    Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4));
                else
                    Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4));
            }
            Console.Out.WriteLine();
        }
        Console.Out.WriteLine();
    }           
  }
}

生成的轰炸模式输出如下（左侧的字段值，右侧的度量）

Round 1:
  2   1   4   2   3   2   6  ||   7  16   8  10   4  18   6
  3   5   3   1   1   1   9  ||  11  18  18  21  17  28   5
  4  [2]  4   2   3   4   1  ||  19 [32] 21  20  17  24  22
  7   6   2   4   4   3   6  ||   8  17  20  14  16  22   8
  1   2   1   1   1   2   4  ||  14  15  14  11  13  16   7

Round 2:
  2   1   4   2   3   2   6  ||   5  13   6   9   4  18   6
  2   4   2   1   1  [1]  9  ||  10  15  17  19  17 [28]  5
  3   2   3   2   3   4   1  ||  16  24  18  17  17  24  22
  6   5   1   4   4   3   6  ||   7  14  19  12  16  22   8
  1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 3:
  2   1   4   2   2   1   5  ||   5  13   6   7   3  15   5
  2   4   2   1   0   1   8  ||  10  15  17  16  14  20   2
  3  [2]  3   2   2   3   0  ||  16 [24] 18  15  16  21  21
  6   5   1   4   4   3   6  ||   7  14  19  11  14  19   6
  1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 4:
  2   1   4   2   2   1   5  ||   3  10   4   6   3  15   5
  1   3   1   1   0   1   8  ||   9  12  16  14  14  20   2
  2   2   2   2   2  [3]  0  ||  13  16  15  12  16 [21] 21
  5   4   0   4   4   3   6  ||   6  11  18   9  14  19   6
  1   2   1   1   1   2   4  ||  10   9  10   9  13  16   7

Round 5:
  2   1   4   2   2   1   5  ||   3  10   4   6   2  13   3
  1   3   1   1   0  [0]  7  ||   9  12  16  13  12 [19]  2
  2   2   2   2   1   3   0  ||  13  16  15  10  14  15  17
  5   4   0   4   3   2   5  ||   6  11  18   7  13  17   6
  1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 6:
  2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
  1   3   1   1   0   0   6  ||   9  12  16  11   8  13   0
  2   2   2   2   0   2   0  ||  13  16  15   9  14  14  15
  5   4  [0]  4   3   2   5  ||   6  11 [18]  6  11  15   5
  1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 7:
  2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
  1   3   1   1   0   0   6  ||   8  10  13   9   7  13   0
  2  [1]  1   1   0   2   0  ||  11 [15] 12   8  12  14  15
  5   3   0   3   3   2   5  ||   3   8  10   3   8  15   5
  1   1   0   0   1   2   4  ||   8   8   7   7   9  13   5

Round 8:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
  0   2   0   1   0   0   6  ||   7   7  12   7   7  13   0
  1   1   0   1   0   2   0  ||   8   8  10   6  12  14  15
  4   2   0   3   3  [2]  5  ||   2   6   8   2   8 [15]  5
  1   1   0   0   1   2   4  ||   6   6   6   7   9  13   5

Round 9:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
  0   2   0   1   0   0   6  ||   7   7  12   7   6  12   0
  1   1   0   1   0  [1]  0  ||   8   8  10   5  10 [13] 13
  4   2   0   3   2   2   4  ||   2   6   8   0   6   9   3
  1   1   0   0   0   1   3  ||   6   6   6   5   8  10   4

Round 10:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  10   1
  0   2  [0]  1   0   0   5  ||   7   7 [12]  7   6  11   0
  1   1   0   1   0   1   0  ||   8   8  10   4   8   9  10
  4   2   0   3   1   1   3  ||   2   6   8   0   6   8   3
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 11:
  2   0   3   1   1   0   4  ||   0   6   0   3   0  10   1
  0   1   0   0   0  [0]  5  ||   4   5   5   5   3 [11]  0
  1   0   0   0   0   1   0  ||   6   8   6   4   6   9  10
  4   2   0   3   1   1   3  ||   1   5   6   0   5   8   3
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 12:
  2   0   3   1   0   0   3  ||   0   6   0   2   1   7   1
  0   1   0   0   0   0   4  ||   4   5   5   4   1   7   0
  1   0   0   0   0  [0]  0  ||   6   8   6   4   5  [9]  8
  4   2   0   3   1   1   3  ||   1   5   6   0   4   7   2
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 13:
  2   0   3   1   0   0   3  ||   0   6   0   2   1   6   0
  0   1   0   0   0   0   3  ||   4   5   5   4   1   6   0
  1  [0]  0   0   0   0   0  ||   6  [8]  6   3   3   5   5
  4   2   0   3   0   0   2  ||   1   5   6   0   4   6   2
  1   1   0   0   0   1   3  ||   6   6   6   3   4   4   0

Round 14:
  2   0   3   1   0  [0]  3  ||   0   5   0   2   1  [6]  0
  0   0   0   0   0   0   3  ||   2   5   4   4   1   6   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   5   5
  3   1   0   3   0   0   2  ||   0   4   5   0   4   6   2
  1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 15:
  2   0   3   1   0   0   2  ||   0   5   0   2   1   4   0
  0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   4   4
  3   1   0   3   0  [0]  2  ||   0   4   5   0   4  [6]  2
  1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 16:
  2  [0]  3   1   0   0   2  ||   0  [5]  0   2   1   4   0
  0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
  3   1   0   3   0   0   1  ||   0   4   5   0   3   3   1
  1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 17:
  1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
  3   1  [0]  3   0   0   1  ||   0   4  [5]  0   3   3   1
  1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 18:
  1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   3   3   2   2   2   3   3
  3  [0]  0   2   0   0   1  ||   0  [4]  2   0   2   3   1
  1   0   0   0   0   0   2  ||   2   4   2   2   2   3   0

Round 19:
  1   0   2   1   0  [0]  2  ||   0   3   0   1   1  [4]  0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   3   3
  2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 20:
  1  [0]  2   1   0   0   1  ||   0  [3]  0   1   1   2   0
  0   0   0   0   0   0   1  ||   1   3   3   3   1   2   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
  2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 21:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
  2   0   0   2   0  [0]  1  ||   0   2   2   0   2  [3]  1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 22:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
 [0]  0   0   0   0   0   0  ||  [2]  2   2   2   2   1   1
  2   0   0   2   0   0   0  ||   0   2   2   0   2   1   1
  0   0   0   0   0   0   1  ||   2   2   2   2   2   1   0

Round 23:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0  [0]  0   0   0   1  ||   0   1  [2]  2   1   2   0
  0   0   0   0   0   0   0  ||   1   1   2   2   2   1   1
  1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
  0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 24:
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0  [0]  0   0   0   0  ||   1   1  [2]  2   2   1   1
  1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
  0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 25:
  0   0   0   0   0  [0]  1  ||   0   0   0   0   0  [2]  0
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0   0   0   0   0   0  ||   1   1   1   1   1   1   1
  1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
  0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 26:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
 [0]  0   0   0   0   0   0  ||  [1]  1   1   1   1   0   0
  1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
  0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 27:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0  [0]  0   0   0   0  ||   0   0  [1]  1   1   0   0
  0   0   0   1   0   0   0  ||   0   0   1   0   1   1   1
  0   0   0   0   0   0   1  ||   0   0   1   1   1   1   0

Round 28:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0  [0]  0  ||   0   0   0   0   0  [1]  1
  0   0   0   0   0   0   1  ||   0   0   0   0   0   1   0

Done in 28 rounds

score 1 · Accepted Answer

蛮力！

我知道它效率不高，但即使你找到了一个更快的算法，你也可以随时测试这个结果以了解它的准确度。

使用一些递归，如下所示：

void fn(tableState ts, currentlevel cl)
{
  // first check if ts is all zeros yet, if not:
  //
  // do a for loop to go through all cells of ts, 
  // for each cell do a bomb, and then
  // call: 
  // fn(ts, cl + 1);

}

您可以通过缓存来提高效率，如果不同的方式导致相同的结果，则不应重复相同的步骤。

详细说明：

如果轰炸单元格 1,3,5 导致与轰炸单元格 5,3,1 相同的结果，那么，对于这两种情况，您不应该再次重新执行所有后续步骤，只有 1 就足够了，您应该将所有内容存储在某个地方表状态并使用其结果。

表统计信息的散列可用于进行快速比较。

score 1 · Accepted Answer

我也有28个动作。我使用了两个测试来确定最好的下一步：首先是产生棋盘最小和的棋步。其次，对于相等的和，产生最大密度的移动，定义为：

number-of-zeros / number-of-groups-of-zeros

这是哈斯克尔。“解决板”显示引擎的解决方案。您可以通过输入“main”来玩游戏，然后输入目标点，“best”表示推荐，或“quit”表示退出。

输出：
*Main> 求解板
[(4,4),(3,6),(3,3),(2,2),(2,2),(4,6),(4,6), (2,6),(3,2),(4,2),(2,6),(3,3),(4,3),(2,6),(4,2),(4 ,6),(4,6),(3,6),(2,6),(2,6),(2,4),(2,4),(2,6),(3,6 ),(4,2),(4,2),(4,2),(4,2)]

import Data.List
import Data.List.Split
import Data.Ord
import Data.Function(on)

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]

n = 5
m = 7

updateBoard board pt =
  let x = fst pt
      y = snd pt
      precedingLines = replicate ((y-2) * n) 0
      bomb = concat $ replicate (if y == 1
                                    then 2
                                    else min 3 (m+2-y)) (replicate (x-2) 0 
                                                         ++ (if x == 1 
                                                                then [1,1]
                                                                else replicate (min 3 (n+2-x)) 1)
                                                                ++ replicate (n-(x+1)) 0)
  in zipWith (\a b -> max 0 (a-b)) board (precedingLines ++ bomb ++ repeat 0)

showBoard board = 
  let top = "   " ++ (concat $ map (\x -> show x ++ ".") [1..n]) ++ "\n"
      chunks = chunksOf n board
  in putStrLn (top ++ showBoard' chunks "" 1)
       where showBoard' []     str count = str
             showBoard' (x:xs) str count =
               showBoard' xs (str ++ show count ++ "." ++ show x ++ "\n") (count+1)

instances _ [] = 0
instances x (y:ys)
  | x == y    = 1 + instances x ys
  | otherwise = instances x ys

density a = 
  let numZeros = instances 0 a
      groupsOfZeros = filter (\x -> head x == 0) (group a)
  in if null groupsOfZeros then 0 else numZeros / fromIntegral (length groupsOfZeros)

boardDensity board = sum (map density (chunksOf n board))

moves = [(a,b) | a <- [2..n-1], b <- [2..m-1]]               

bestMove board = 
  let lowestSumMoves = take 1 $ groupBy ((==) `on` snd) 
                              $ sortBy (comparing snd) (map (\x -> (x, sum $ updateBoard board x)) (moves))
  in if null lowestSumMoves
        then (0,0)
        else let lowestSumMoves' = map (\x -> fst x) (head lowestSumMoves) 
             in fst $ head $ reverse $ sortBy (comparing snd) 
                (map (\x -> (x, boardDensity $ updateBoard board x)) (lowestSumMoves'))   

solve board = solve' board [] where
  solve' board result
    | sum board == 0 = result
    | otherwise      = 
        let best = bestMove board 
        in solve' (updateBoard board best) (result ++ [best])

main :: IO ()
main = mainLoop board where
  mainLoop board = do 
    putStrLn ""
    showBoard board
    putStr "Pt: "
    a <- getLine
    case a of 
      "quit"    -> do putStrLn ""
                      return ()
      "best"    -> do putStrLn (show $ bestMove board)
                      mainLoop board
      otherwise -> let ws = splitOn "," a
                       pt = (read (head ws), read (last ws))
                   in do mainLoop (updateBoard board pt)

score 0 · Accepted Answer

这是对第一个问题的回答。我没有注意到他改变了参数。

创建所有目标的列表。根据受跌落影响的正值的数量（本身和所有邻居）为目标分配一个值。最高值将是九。

按受影响目标的数量对目标进行排序（降序），对每个受影响目标的总和进行二次降序排序。

向排名最高的目标投掷炸弹，然后重新计算目标并重复，直到所有目标值都为零。

同意，这并不总是最佳的。例如，

这种方法需要 5 颗炸弹才能清除。不过，最理想的情况是，您可以在 4 内完成。不过，非常接近并且没有回溯。对于大多数情况，它将是最佳的，或者非常接近。

使用原始问题编号，这种方法解决了 28 个炸弹。

添加代码来演示这种方法（使用带有按钮的表单）：

         private void button1_Click(object sender, EventArgs e)
    {
        int[,] matrix = new int[10, 10] {{5, 20, 7, 1, 9, 8, 19, 16, 11, 3}, 
                                         {17, 8, 15, 17, 12, 4, 5, 16, 8, 18},
                                         { 4, 19, 12, 11, 9, 7, 4, 15, 14, 6},
                                         { 17, 20, 4, 9, 19, 8, 17, 2, 10, 8},
                                         { 3, 9, 10, 13, 8, 9, 12, 12, 6, 18}, 
                                         {16, 16, 2, 10, 7, 12, 17, 11, 4, 15},
                                         { 11, 1, 15, 1, 5, 11, 3, 12, 8, 3},
                                         { 7, 11, 16, 19, 17, 11, 20, 2, 5, 19},
                                         { 5, 18, 2, 17, 7, 14, 19, 11, 1, 6},
                                         { 13, 20, 8, 4, 15, 10, 19, 5, 11, 12}};


        int value = 0;
        List<Target> Targets = GetTargets(matrix);
        while (Targets.Count > 0)
        {
            BombTarget(ref matrix, Targets[0]);
            value += 1;
            Targets = GetTargets(matrix);
        }
        Console.WriteLine( value);
        MessageBox.Show("done: " + value);
    }

    private static void BombTarget(ref int[,] matrix, Target t)
    {
        for (int a = t.x - 1; a <= t.x + 1; a++)
        {
            for (int b = t.y - 1; b <= t.y + 1; b++)
            {
                if (a >= 0 && a <= matrix.GetUpperBound(0))
                {
                    if (b >= 0 && b <= matrix.GetUpperBound(1))
                    {
                        if (matrix[a, b] > 0)
                        {
                            matrix[a, b] -= 1;
                        }
                    }
                }
            }
        }
        Console.WriteLine("Dropped bomb on " + t.x + "," + t.y);
    }

    private static List<Target> GetTargets(int[,] matrix)
    {
        List<Target> Targets = new List<Target>();
        int width = matrix.GetUpperBound(0);
        int height = matrix.GetUpperBound(1);
        for (int x = 0; x <= width; x++)
        {
            for (int y = 0; y <= height; y++)
            {
                Target t = new Target();
                t.x = x;
                t.y = y;
                SetTargetValue(matrix, ref t);
                if (t.value > 0) Targets.Add(t);
            }
        }
        Targets = Targets.OrderByDescending(x => x.value).ThenByDescending( x => x.sum).ToList();
        return Targets;
    }

    private static void SetTargetValue(int[,] matrix, ref Target t)
    {
        for (int a = t.x - 1; a <= t.x + 1; a++)
        {
            for (int b = t.y - 1; b <= t.y + 1; b++)
            {
                if (a >= 0 && a <= matrix.GetUpperBound(0))
                {
                    if (b >= 0 && b <= matrix.GetUpperBound(1))
                    {
                        if (matrix[ a, b] > 0)
                        {
                            t.value += 1;
                            t.sum += matrix[a,b];
                        }

                    }
                }
            }
        }

    }

您将需要的课程：

        class Target
    {
        public int value;
        public int sum;
        public int x;
        public int y;
    }

score 0 · Accepted Answer

所有这些问题归结为计算编辑距离。只需计算给定矩阵和零矩阵之间的 Levenshtein 距离的变体，其中编辑被替换为轰炸，使用动态编程来存储中间数组之间的距离。我建议使用矩阵的散列作为键。在伪 Python 中：

memo = {}

def bomb(matrix,i,j):
    # bomb matrix at i,j

def bombsRequired(matrix,i,j):
    # bombs required to zero matrix[i,j]

def distance(m1, i, len1, m2, j, len2):
    key = hash(m1)
    if memo[key] != None: 
        return memo[key]

    if len1 == 0: return len2
    if len2 == 0: return len1

    cost = 0
    if m1 != m2: cost = m1[i,j]
    m = bomb(m1,i,j)
    dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
    memo[key] = dist
    return dist

score 0 · Accepted Answer

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

创建 N 次应用 bomp 的函数
为所有 bompb-placement/bomb-count 可能性创建循环（当 matrix==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[][] 减量代码

score 0 · Accepted Answer

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

我的解决方案是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();
    }

}

algorithm - 炸弹投放算法

32 回答 32

使用分支定界的 Mathematica 整数线性规划

对于任何使用贪心算法阅读本文的人

Related

Reference