炸弹algorithm
我有一个由非负整数组成的nxmmatrix。 例如：
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
“放下炸弹”将目标单元和所有八个邻居的数量减less一个，最less为零。
xxxx X x xxx
什么是algorithm，将确定所需的最小数量的炸弹减less所有单元格为零？
B选项（由于我不是一个仔细的读者）
其实问题的第一个版本不是我正在寻找的答案。 我没有仔细阅读整个任务，还有额外的限制，让我们说：
那简单的问题呢，在sorting时必须不增加：
8 7 6 6 5是可能的input顺序
7 8 5 5 2是不可能的，因为7 – > 8在一个序列中生长。
也许find答案“更容易”的情况下，将有助于find更难的解决scheme。
PS：我相信当我们有几个相同的情况需要最小的炸弹来清除上线时，我们select一个在行左边使用的炸弹。 还有任何证据可能是正确的？
有一种方法可以将其简化为一个简单的子问题。
解释有两部分，algorithm，以及algorithm提供最优解的原因。 如果没有第二个，第一个就没有意义了，所以我会从这个开始。
如果你想到轰炸矩形（假设一个大的矩形 – 没有边缘的情况下），你可以看到，要减less周长的空心矩形为0的唯一方法是炸弹的周长或炸弹的空心矩形正方形在正方形里面。 我将调用周边图层1，并在其中的矩形2层。
一个重要的见解是没有第1层炸弹，因为这样做的“爆炸半径”总是包含在第2层的另一个正方形的爆炸半径内。你应该能够很容易地说服自己。
所以，我们可以把问题减less到寻找一个最佳的方式来炸毁外围，然后我们可以重复，直到所有的方块都是0。
但是，当然，如果有可能以不太理想的方式轰炸外围，那么并不总能find一个最佳的解决scheme，但是通过使用X个额外的炸弹使得通过X个炸弹简化内层的问题变得更为简单。 所以，如果我们把第一层称为许可层，那么如果我们在第二层（第一层）的某个地方放置一个额外的X炸弹，我们是否可以减less后来轰炸第二层的努力超过X？ 换句话说，我们必须certificate我们可以贪心减less外围。
但是，我们知道我们可以是贪婪的。 因为没有第二层中的炸弹可以比第3层中的有战略意义的炸弹更有效地减less第2层到第0层。并且出于同样的原因 – 总是有一个炸弹放在第3层，这会影响到每一个方块第二层炸弹放置在第二层可以。 所以，它永远不会伤害我们的贪婪（在这种贪婪的意义上）。
所以我们所要做的就是find最佳的方法，通过轰炸下一个内层来将许可证降到0。
我们从来没有受到伤害，首先轰炸angular落为0，因为只有内层的angular落才能到达它，所以我们没有select（而且，任何可以到达angular落的炸弹的爆炸半径包含在从内层angular落的爆炸半径）。
一旦我们这样做了，与0angular相邻的边界上的方格只能从内层方向到达2个方格：
0 AB CXY DZ
在这一点上，周边实际上是一个闭合的1维环，因为任何炸弹都会减less3个相邻的正方形。 除了angular落附近的一些奇怪 – X可以“打”A，B，C和D.
现在我们不能使用任何爆炸半径技巧 – 除了怪异的angular落之外，每个正方形的情况是对称的，甚至没有爆炸半径是另一个的子集。 请注意，如果这是一条线（正如Panic上校所讨论的），而不是一个闭环，那么解决scheme是微不足道的。 终点必须减less到0，并且永远不会伤害你轰炸终点附近的点，也是因为爆炸半径是一个超集。 一旦你把端点设置为0，你仍然有一个新的端点，所以重复（直到全部为0）。
所以，如果我们可以最优化地将图层中的单个正方形减less到0，那么我们有一个algorithm（因为我们已经切割了这个循环，现在有一个直线与终点）。 我相信在最低价值的广场附近轰炸（给你2个选项），使得最低值的2个方格内的最高值是最小的可能（你可能不得不拆分你的轰炸来pipe理这个）是最优的，但是我（还没有？）有证据。
Pólya说：“如果你不能解决问题，那么你可以解决一个更容易的问题：find它。
一维问题（当网格是单行时）显而易见的更简单的问题。 我们从最简单的algorithm开始 – 贪婪地轰炸最大的目标。 这是什么时候出错？
给定1 1 1 ，贪婪algorithm对它首先被轰炸的单元无动于衷。 当然，中心细胞更好 – 它一次消耗所有三个细胞。 这表明一个新的algorithmA，“炸弹，以尽量减less剩余的总和”。 这个algorithm什么时候出错？
给定1 1 2 1 1 ，algorithmA在轰炸第二，第三或第四个单元之间是无差别的。 但轰炸第二格离开0 0 1 1 1要好于轰炸第三格离开1 0 1 0 1 。 如何解决这个问题？ 轰炸第三个牢房的问题是，它让我们在左边工作，在右边工作，必须分开进行。
怎么样“的炸弹，以尽量减less剩余的金额，但最大限度的左侧（我们被炸的地方）加上最低的权利”。 调用这个algorithmB.这个algorithm什么时候出错？
编辑：在阅读评论后，我同意一个更有趣的问题将是一维问题的变化，以便两端join。 希望看到有任何进展。
我不得不停下来只是一个部分的解决scheme，因为我已经没时间了，但是希望这个部分解决scheme能够提供一些解决这个问题的可能方法的一些见解。
面对一个棘手的问题时，我想提出一个简单的问题来发展一个关于问题空间的直觉。 在这里，我所采取的第一步是将这个二维问题归结为一维问题。 考虑一下：
0 4 2 1 3 0 1
无论如何，你知道你需要在4点或其附近进行4次炸弹，以使其降到0点。由于剩下的点数是较低的，所以轰炸0或4轰炸机没有任何好处。 2 。 事实上，我相信（但是没有一个严格的证据），轰炸2直到4点下降到0，至less和其他策略一样好，让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
从一个需要某种方式的数字开始的想法是一个吸引人的想法，因为突然之间可以find一个解决scheme，作为一些人声称至less与其他解决scheme一样好 。
董事会边缘的下一步复杂的search至less仍然是可行的。 我清楚地看到，轰炸外缘绝对没有任何好处。 你最好把现场轰炸一下，并免费获得另外三个空间。 鉴于此，我们可以说轰炸边缘内的一个环至less和轰炸边缘一样好 。 而且，我们可以将这一点与直觉相结合：轰炸边缘内部的正确边界实际上是使边缘空间下降到0的唯一方法。更重要的是，找出最优策略是非常简单的（因为它是在至less和其他策略一样好）把angular点数降到0.我们把这一切放在一起，可以更接近二维空间的解决scheme。
考虑到关于angular落的观察，我们可以肯定地说，我们知道从任何出发板到全局angular度都是零的棋盘的最佳策略。 这是一个这样的董事会的例子（我借用了上面两个线性板的数字）。 我已经标记了一些空格，我会解释为什么。
0 4 2 1 3 0 1 0 4 xxxxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 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]xxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 0 3 1 0 3 0 1 0 4 x[x]xxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 0 2 0 0 3 0 1 0 4 x[x]xxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 0 1 0 0 3 0 1 0 4 x[x]xxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 0 0 0 0 3 0 1 0 4 xxxxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0
这种方法的缺陷在最后两次爆炸中变得非常明显。 很显然，由于第二排第一列减less四位数的唯一炸弹场是第一个x和y 。 最后两个爆炸案明显不如轰炸第一个x ，这个爆炸物的爆炸情况完全相同（关于第一排的第一个爆炸点，我们没有其他办法）。 既然我们已经certificate我们目前的策略是不理想的，那么显然需要对策略进行修改。
在这一点上，我可以退后一步，把注意力集中在一个angular落。 我们来考虑一下：
0 4 2 1 4 xya 2 z . . 1 b . .
很显然，让空间降到零的唯一方法是轰炸一些x ， y和z 。 在我心中有一些杂技，我相当肯定最好的解决办法是炸三次，然后再炸a 。 现在要弄清楚我是如何达到这个解决scheme的，如果它揭示出我们甚至可以用来解决当地问题的直觉。 我注意到，没有轰炸的y和z空间。 试图find一个angular落轰炸这些空间有道理产生一个angular落，看起来像这样：
0 4 2 5 0 4 xya . 2 z . . . 5 b . . . 0 . . . .
对于这个，我很清楚最好的解决办法是炸5次，5次。 我们再走一步。
0 4 2 5 6 0 0 4 xya . . . 2 z . . . . . 5 b . . . . . 6 . . . . . . 0 . . . . . . 0 . . . . . .
在这里，感觉同样直观，最佳的解决scheme是炸a和b六次然后四次。
现在，它变成了一个如何把这些直觉变成我们可以build立的原则的游戏。
希望继续！
对于更新的问题，简单的贪婪algorithm会给出最佳结果。
将A [0,0]炸弹投入单元格A [1,1]，然后将A [1,0]炸弹投入单元格A [2,1]，然后继续向下。 为了清理左下angular，将最大值（A [N-1,0]，A [N-2,0]，A [N-3,0]）投入单元格A [N-2,1]。 这将完全清理前3列。
用同样的方法清洁3,4,5，然后是6,7,8等。
不幸的是，这并不能解决原始问题。
“更大”的问题（没有“非约束”约束）可能被certificate是NP难的。 这是一个certificate的草图。
假设我们有一个等级为3的平面图。让我们find这个图的最小顶点覆盖 。 根据维基百科的文章，这个问题对于平面图度数达到3的NP难度。这可以通过从Planar 3SAT减less来certificate。 平面3SAT的硬度 – 从3SAT减less。 这两个certificate都在最近由教授“algorithm下界”讲授。 Erik Demaine（讲座7和9）。
如果我们将原始图的一些边（图中的左侧图）分开，每一个都有偶数个附加节点，则结果图（图中的右侧图）应该对原始顶点具有完全相同的最小顶点覆盖。 这样的转换允许将图顶点alignment到网格上的任意位置。
如果我们只将图顶点放在偶数行和列上（这样，一个顶点没有两个边形成一个锐angular），在有边的地方插入“ones”，向其他网格位置插入“0”我们可以使用原始问题的任何解决scheme来find最小的顶点覆盖。
您可以将此问题表示为整型编程问题。 （这只是解决这个问题的可能解决scheme之一）
有几点：
abcd efgh ijkl mnop
你可以写16个方程，例如f点
f <= ai + bi + ci + ei + fi + gi + ii + ji + ki
最小化所有指标和整数解的总和。
解决scheme当然是这个指标的总和。
这可以通过在边界0上设置所有的xi来进一步简化，所以在这个例子中最终有4 + 1个方程。
问题在于解决这样的问题没有小事。 我不是这方面的专家，但作为线性规划解决这个问题是困难的NP。
这是一个部分的答案，我试图find一个下限和上限，可能是炸弹的可能数量。
在3×3和更小的电路板中，解决scheme始终是最大编号的单元。
在大于4×4的棋盘上，第一个明显的下限是angular落的总和：
*2* 3 7 *1* 1 5 6 2 2 1 3 2 *6* 9 6 *4*
然而，你安排的炸弹，这是不可能清除这个4×4板less于2 + 1 + 6 + 4 = 13炸弹。
在其他的回答中已经提到，把炸弹放在二次angular落消除angular落永远不会比把炸弹放在angular落本身更糟，所以给予董事会：
*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*
我们可以通过在第二个angular落放置炸弹给出一个新的委员会，
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枚炸弹来清理angular落。
现在观察下面标记的数字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，所以增加了我们用来清除angular的炸弹数量，这张地图所需的炸弹数量已经变成了28枚炸弹。 用不到28枚炸弹清除地图是不可能的，这是这张地图的下界。
你可以使用贪心algorithm来build立一个上界。 其他答案表明，贪婪的algorithm会产生一个使用28个炸弹的解决scheme。 由于我们早先已经certificate，没有最佳解决scheme的炸弹less于28枚，因此28枚炸弹的确是最佳解决scheme。
当贪心和find上面提到的最小范围的方法不会收敛的时候，我想你必须回去检查所有的组合。
find下界的algorithm如下：
- 选取数字最高的元素，将其命名为P.
- 将所有的单元格从P和P本身两步标记为不可取的。
- 将P添加到
minimums列表。 - 重复步骤1，直到所有单元格都是不可取的。
- 求
minimums列表来得到下限。
这将是一个贪婪的方法：
-
计算一个n×m阶的“分数”matrix，其中score [i] [j]是在位置（i，j）被轰炸的情况下matrix中的点的总减法。 （最高分为9分，最低分为0分）
-
移动明智的行，find并选出最高分的第一个位置（比如（i，j））。
-
炸弹（我，j）。 增加炸弹计数。
-
如果原始matrix的所有元素都不为零，则转到1。
我怀疑这是最佳解决scheme。
编辑：
我上面发布的贪婪方法虽然有效，但很可能并不能给我们提供最佳解决scheme。 所以我想应该给它增加一些DP元素。
我认为我们可以同意，在任何时候，如果（i，j）被轰炸，最高“得分”（得分[i] [j] =全部扣分）的位置之一必须是有针对性的。 从这个假设开始，下面是新的方法：
NumOfBombs（M）：（返回所需的最小爆炸次数）
-
给定n×m的matrixM. 如果M的所有元素均为零，则返回0。
-
计算“分数”matrixM.
设k个不同的位置P1，P2，… Pk（1 <= k <= n * m）为M中位置最高的位置。
-
（1 + min（NumOfBombs（M1），NumOfBombs（M2），…，NumOfBombs（Mk）））
如果我们分别轰炸位置P1，P2，…，Pk，则M1，M2，…，Mk是结果matrix。
而且，如果我们想要除此之外的头寸的sorting，我们将不得不跟踪“min”的结果。
你的新问题，跨行非递减值，很容易解决。
注意到左栏包含最高的数字。 因此，任何最佳解决scheme都必须首先将此列减less到零。 因此，我们可以对这一列执行一维轰炸，将其中的每一个元素都归零。 我们让炸弹落在第二列，以便造成最大的伤害。 这里有很多关于一维情况的post，我想，所以我觉得跳过这种情况是安全的。 （如果你想让我描述一下，我可以）。 由于属性下降，最左边的三列将全部归零。 但是，我们可以在这里使用最less数量的炸弹，因为左列必须被清零。
现在，一旦左列被清零，我们只修剪现在归零的三个最左边的列，并用现在简化的matrix重复。 这必须给我们一个最佳的解决scheme，因为在每一个阶段我们都使用最less数量的炸弹。
没有必要将问题转化为线性子问题。
相反，用一个简单的贪婪的启发式，就是从最大的一个开始。
在给定的例子中，有四个angular{2,1,6,4}。 对于每个angular落来说，最好的办法莫过于把angular落里的单元格对angular线轰炸，所以我们知道一个事实，我们的第一次2 + 1 + 6 + 4 = 13的轰炸必须在这些对angular单元格中。 轰炸之后，我们剩下一个新的matrix：
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 0 2。 现在，我们在第四行有2个新angular{2,1}。 我们炸了那些炸弹，又炸了3次。 我们现在已经把matrix减less到了4×4。 左上angular有一个angular落。 我们炸了。 现在我们还有2个angular落{5，3}。 由于5号是我们最大的一个angular，我们首先炸了5个，然后在另一个angular点炸了3个。 总数是13 + 3 + 3 + 1 + 5 + 3 = 28。
这是通过这个“迷宫”的位置进行广度search的最短path（一系列的爆炸）。 不，我不能certificate没有更快的algorithm，对不起。
#!/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))
看来，线性规划方法在这里可能非常有用。
令P mxn为位置值的matrix：
现在定义一个炸弹matrixB（x，y） mxn ，其中1≤x≤m ， 1≤y≤n如下
以这样的方式
例如：
所以我们正在寻找一个matrixB mxn = [ b ij ]那个
-
可以定义为炸弹matrix的总和：
（那么q ij就是我们在位置p ij下降的炸弹数量 ）
-
p ij – b ij ≤ 0 (to be more succint, let us say it as P – B ≤ 0 )
Also, B should minimize the sum 
。
We can also write B as the ugly matrix ahead:
and since P – B ≤ 0 (which means P ≤ B ) we have the following pretty linear inequality system below:
Being q mn x 1 defined as
p mn x 1 defined as
We can say we have a system The system below represented as product of matrices http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D being S mn x mn the matrix to be reversed to solve the system. I did not expand it myself but I believe it should be easy to do it in code.
Now, we have a minimum problem which can be stated as
I believe it is something easy, almost trivial to be solved with something like the simplex algorithm (there is this rather cool doc about it ). However, I do know almost no linear programming (I will take a course about it on Coursera but it is just in the future…), I had some headaches trying to understand it and I have a huge freelance job to finish so I just give up here. It can be that I did something wrong at some point, or that it can't go any further, but I believe this path can eventually lead to the solution. Anyway, I am anxious for your feedback.
(Special thanks for this amazing site to create pictures from LaTeX expressions )
This greedy solution seems to be correct :
As pointed in comments, it'll fail in 2D. But maybe you may improve it.
For 1D:
If there is at least 2 numbers you don't need to shoot to the leftmost one because shooting to the second is not worse . So shoot to the second, while first isn't 0, because you have to do it. Move to the next cell. Don't forget about last cell.
C++ code:
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]) } }
So for 2D:
Again: you don't need to shoot in the first row (if there is the second). So shoot to the second one. Solve 1D task for first row. (because you need to make it null). Go down. Don't forget last row.
To minimize the number of bombs, we have to maximize effect of every bomb. To achive this, on every step we have to select the best target. For each point summing it and it's eight neighbours – could be used as an efficiency quantity of bombing this point. This will provide close to optimal sequence of bombs.
UPD : We should also take number of zeros into account, becouse bombin them is inefficiently. In fact the problem is to minimize number of hitted zeros. But we can not know how any step gets us closer to this aim. I agree with idea that the problem is NP-complete. I sugest a greedy approach, which will give an answer close to real.
I believe that to minimize the amount of bombs you simply need maximize the amount of damage.. for that to happen need to check the area that has the strongest force.. so you first analyze the field with a 3×3 kernel and check where the sum is stronger.. and bomb there.. and do until the field is flat.. for this filed the answer is 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');
Here is a solution that generalizes the good properties of the corners.
Let's assume that we could find a perfect drop point for a given field, that is, a best way to decrease the value in it. Then to find the minimum number of bombs to be dropped, a first draft of an algorithm could be (the code is copy-pasted from a ruby implementation):
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
The challenge is choose_a_perfect_drop_point . First, let's define what a perfect drop point is.
- A drop point for
(x, y)decreases the value in(x, y). It may also decrease values in other cells. - A drop point a for
(x, y)is better than a drop point b for(x, y)if it decreases the values in a proper superset of the cells that b decreases. - A drop point is maximal if there is no other better drop point.
- Two drop points for
(x, y)are equivalent if they decrease the same set of cells. - A drop point for
(x, y)is perfect if it is equivalent to all maximal drop points for(x, y).
If there is a perfect drop point for (x, y) , you cannot decrease the value at (x, y) more effectively than to drop a bomb on one of the perfect drop points for (x, y) .
A perfect drop point for a given field is a perfect drop point for any of its cells.
Here are few examples:
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
The perfect drop point for the cell (0, 0) (zero-based index) is (1, 1) . All other drop points for (1, 1) , that is (0, 0) , (0, 1) , and (1, 0) , decrease less cells.
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
A perfect drop point for the cell (2, 2) (zero-based index) is (2, 2) , and also all the surrounding cells (1, 1) , (1, 2) , (1, 3) , (2, 1) , (2, 3) , (3, 1) , (3, 2) , and (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
a perfect drop points for the cell (2, 2) is (3, 1) : It decreases the value in (2, 2) , and the value in (4, 0) . All other drop points for (2, 2) are not maximal, as they decrease one cell less. The perfect drop point for (2, 2) is also the perfect drop point for (4, 0) , and it is the only perfect drop point for the field. It leads to the perfect solution for this field (one bomb drop).
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
There is no perfect drop point for (2, 2) : Both (1, 1) and (1, 3) decrease (2, 2) and another cell (they are maximal drop points for (2, 2) ), but they are not equivalent. However, (1, 1) is a perfect drop point for (0, 0) , and (1, 3) is a perfect drop point for (0, 4) .
With that definition of perfect drop points and a certain order of checks, I get the following result for the example in the question:
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
However, the algorithm only works if there is at least one perfect drop point after each step. It is possible to construct examples where there are no perfect drop points:
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
For these cases, we can modify the algorithm so that instead of a perfect drop point, we choose a coordinate with a minimal choice of maximal drop points, then calculate the minimum for each choice. In the case above, all cells with values have two maximal drop points. For example, (0, 1) has the maximal drop points (1, 1) and (1, 2) . Choosing either one and then calcualting the minimum leads to this result:
Drop bomb on 1, 1 Drop bomb on 2, 2 Drop bomb on 1, 2 Drop bomb on 2, 1 2
Here's another idea:
Let's start by assigning a weight to each space on the board for how many numbers would be reduced by dropping a bomb there. So if the space has a non-zero number, it gets a point, and if any space adjacent to it has a non-zero number, it gets an additional point. So if there is a 1000-by-1000 grid, we have a weight assigned to each of the 1 million spaces.
Then sort the list of spaces by weight, and bomb the one with the highest weight. This is getting the most bang for our buck, so to speak.
After that, update the weight of every space whose weight is affected by the bomb. This will be the space you bombed, and any space immediately adjacent to it, and any space immediately adjacent to those. In other words, any space which could have had its value reduced to zero by the bombing, or the value of a neighboring space reduced to zero.
Then, re-sort the list spaces by weight. Since only a small subset of spaces had their weight changed by the bombing, you won't need to resort the whole list, just move those ones around in the list.
Bomb the new highest weight space, and repeat the procedure.
This guarantees that every bombing reduces as many spaces as possible (basically, it hits as few spaces which are already zero as possible), so it would be optimal, except that their can be ties in weights. So you may need to do some back tracking when there is a tie for the top weight. Only a tie for the top weight matters, though, not other ties, so hopefully it's not too much back-tracking.
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.
Mathematica Integer Linear Programming using branch-and-bound
As it has already been mentioned, this problem can be solved using integer linear programming (which is NP-Hard ). Mathematica already has ILP built in. "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." [see Constrained Optimization Tutorial in Mathematica.. ]
I've written the following code that utilizes ILP libraries of Mathematica. It is surprisingly fast.
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}]]];]
For the example provided in the problem:
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]
输出
For anyone reading this with a greedy algorithm
Try your code on the following 10×10 problem:
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
Here it is comma-seperated:
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
For this problem, my solution contains 208 bombs. Here's a possible solution (I was able to solve this in about 12 seconds).
As a way to test the results Mathematica is producing, see if your greedy algorithm can do any better.
Well, suppose we number the board positions 1, 2, …, nx 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 nxm 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 nxm 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.
If you want the absolute optimal solution to clean the board you will have to use classic backtracking, but if the matrix is very big it will take ages to find the best solution, if you want an "possible" optimal solution you can use greedy algorithm, if you need help writing the algorithm i can help you
Come to think of it that is the best way. Make another matrix there you store the points you remove by dropping a bomb there then chose the cell with maximum points and drop the bomb there update the points matrix and continue. 例：
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))
cell value +1 for every adjacent cell with a value higher than 0
Brute Force !
I know it is not efficient, but even if you find a faster algorithm, you can always test against this result to know how accurate it is.
Use some recursion, like this:
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); }
You can make this more efficient by caching, if different way lead to same result, you shouldn't repeat the same steps.
To elaborate:
if bombing cell 1,3,5 leads to the same result as bombing cell 5,3,1 , then, you shouldn't re-do all the next steps again for both cases, only 1 is enough, you should store somewhere all table states and use its results.
A hash of table stats can be used to do fast comparison.
- Never bomb border (unless square does not have nonborder neighbour)
- Zero corner.
- To zero corner, drop value of corner one square away diagonaly (the only nonborder neighbour)
- This will create new corners. Go to 2
Edit: did not notice that Kostek suggested almost same approach, so now I make stronger claim: If corners to clear are chosen to be always on outermost layer, then it is optimal.
In OP's example: dropping 2 (as 1+1 or 2) on anything else than on 5 does not leads to hitting any square that dropping on 5 would hit. So we simply must drop 2 on 5 (and 6 on lower left 1 …)
After this, there is only one way how to clear (in top left) corner what was originaly 1 (now 0), and that is by dropping 0 on B3 (excel like notation). 等等。
Only after clearing whole A and E columns and 1 and 7 rows, start clearing one layer deeper.
Consider cleared only those intentionaly cleared, clearing 0 value corners costs nothing and simplifies thinking about it.
Because all bombs dropped this way must be dropped and this leads to cleared fields, it is optimal solution.
After good sleep I realized that this is not true. Consider
ABCDE 1 01000 2 10000 3 00000 4 00000
My approach would drop bombs on B3 and C2, when dropping on B2 would be enough
Here's my solution.. I won't write it out in code yet since I don't have time, but I believe this should produce an optimal number of moves each time – though I'm not sure how efficient it would be at finding the points to bomb.
Firstly, as @Luka Rahne stated in one of the comments, the order in which you bomb is not important- only the combination.
Secondly, as many others have stated, bombing 1-off the diagonal from the corners is optimal because it touches more points than the corners.
This generates the basis for my version of the algorithm: We can bomb the '1-off from the corners' first or last, it doesn't matter (in theory) We bomb those first because it makes later decisions easier (in practice) We bomb the point which affects the most points, while simultaneously bombing those corners.
Let's define Points Of Resistance to be the points in the board with the most non-bombable points + largest number of 0's around them
non-bombable points can be defined as points which don't exist in our current scope of the board we're looking at.
I'll also define 4 bounds which will handle our scope: Top=0, Left=0, Bottom=k,right=j. (values to start)
Finally, I'll define optimal bombs as bombs which are dropped on points that are adjacent to points of resistance and are touching (1) the highest valued point of resistance and (2) the largest number of points possible.
Regarding the approach- it's obvious we're working from the outside in. We will be able to work with 4 'bombers' at the same time.
The first points of resistance are obviously our corners. The 'out of bound' points are not bombable (there are 5 points outside the scope for each corner). So we bomb the points diagonally one off the corners first.
algorithm：
- Find the 4 optimal bomb points.
- If a bomb point is bombing a resistance point which is touching 2 bounds (ie a corner), bomb till that point is 0. Otherwise, bomb each until one of the points of resistance touching the optimal bomb point is 0.
- for each bound: if(sum(bound)==0) advance bound
repeat until TOP=BOTTOM and LEFT=RIGHT
I will try to write the actual code later
You could use state space planning. For example, using A* (or one of its variants) coupled with an heuristic f = g + h like this:
- g: number of bombs dropped so far
- h: sum over all values of the grid divided by 9 (which is the best result, meaning we have an admissible heuristics)
I got 28 moves as well. I used two tests for the best next move: first the move producing the minimum sum for the board. Second, for equal sums, the move producing the maximum density, defined as:
number-of-zeros / number-of-groups-of-zeros
This is Haskell. "solve board" shows the engine's solution. You can play the game by typing "main", then enter a target point, "best" for a recommendation, or "quit" to quit.
OUTPUT：
*Main> solve board
[(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 (\ab -> max 0 (ab)) 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)
There seems to be a nonbipartite matching substructure here. Consider the following instance:
0010000 1000100 0000001 1000000 0000001 1000100 0010000
The optimal solution to this case has size 5 since that's the size of a minimum cover of the vertices of a 9-cycle by its edges.
This case, in particular, shows that the linear programming relaxation a few people have posted isn't exact, doesn't work, and all those other bad things. I'm pretty sure I can reduce "cover the vertices of my planar cubic graph by as few edges as possible" to your problem, which makes me doubt whether any of the greedy/hill-climbing solutions are going to work.
I don't see a way to solve this in polynomial time in the worst case. There might be a very clever binary-search-and-DP solution that I'm not seeing.
EDIT : I see that the contest ( http://deadline24.pl ) is language-agnostic; they send you a bunch of input files and you send them outputs. So you don't need something that runs in worst-case polynomial time. In particular, you get to look at the input !
There are a bunch of small cases in the input. Then there's a 10×1000 case, a 100×100 case, and a 1000×1000 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 1000×1000; the LP relaxation happens to have an integral optimal solution. My solutions agree with the .ans files provided in the test data bundle.
I'd bet you can use the structure of the input in a much more direct way than I did if you took a look at it; seems like you can just pare off the first row, or two, or three repeatedly until you've got nothing left. (Looks like, in the 1000×1000, all of the rows are nonincreasing? I guess that's where your "part B" comes from? )
I can't think of a way to calculate the actual number without just computing the bombing campaign using my best heuristic and hope I get a reasonable result.
So my method is to compute a bombing efficiency metric for each cell, bomb the cell with the highest value, …. iterate the process until I've flattened everything. Some have advocated using simple potential damage (ie score from 0 to 9) as a metric, but that falls short by pounding high value cells and not making use of damage overlap. I'd calculate cell value - sum of all neighbouring cells , reset any positive to 0 and use the absolute value of anything negative. Intuitively this metric should make a selection that help maximise damage overlap on cells with high counts instead of pounding those directly.
The code below reaches total destruction of the test field in 28 bombs (note that using potential damage as metric yields 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 - ie 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(); } } }
The resulting bombing pattern is output as follows (field values on the left, metric on the right)
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
This can be solved using a tree of depth O(3^(n)). Where n is the sum of all of the squares.
First consider that it is trivial to solve the problem with a tree of O(9^n), simply consider all of the possible bombing locations. For an example see Alfe's implementation .
Next realize that we can work to bomb from the bottom up and still get a minimum bombing pattern.
- 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.
This algorithm is correct because
- It is necessary to complete each row at some point.
- Completing a row always requires a play either one above, one below, or within that row.
- It is always as good or better to choose a play one above the lowest uncleared row than a play on the row or below the row.
In practice this algorithm will regularly do better than its theoretical maximum because it will regularly bomb out neighbors and reduce the size of the search. If we assume that each bombing decreases the value of 4 additional targets, then our algorithm will run in O(3^(n/4)) or approximately 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.
evaluation function, total sum:
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]; }
objective function:
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; }
destroy function:
void destroy (int ** matrix, int width, int height, Point p) { int x = px; int y = py; 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]--; } }
goal function:
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; }
linear maximization function:
void solve (int ** matrix, int width, int height) { while (!isGoal(matrix,width,height)) { destroy(matrix,width,height, bestState(matrix,width,height)); } }
This is not optimal, but can be optimized through finding a better evaluation function ..
.. but thinking about this problem, I was thinking that one of the main issues is getting abandoned figures in the middle of zeroes at some point, so I'd take another approach .. which is dominate minimal values into zero, then try to escape zeroes as possible, which lead to general minimization of minimal existing value(s) or so
All this problem boils down to is computing an edit distance. Simply calculate a variant of the Levenshtein distance between the given matrix and the zero matrix, where edits are replaced with bombings, using dynamic programming to store the distances between intermediate arrays. I suggest using a hash of the matrices as a key. In pseudo-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
This was an answer to the first asked question. I hadn't noticed that he changed the parameters.
Create a list of all targets. Assign a value to the target based on the number of positive values impacted by a drop (itself, and all neighbors). Highest value would be a nine.
Sort the targets by the number of targets impacted (Descending), with a secondary descending sort on the sum of each impacted target.
Drop a bomb on the highest ranked target, then re-calculate targets and repeat until all target values are zero.
Agreed, this is not always the most optimal. 例如，
100011 011100 011100 011100 000000 100011
This approach would take 5 bombs to clear. Optimally, though, you could do it in 4. Still, pretty darn close and there is no backtracking. For most situations it will be optimal, or very close.
Using the original problem numbers, this approach solves in 28 bombs.
Adding code to demonstrate this approach (using a form with a button):
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 = tx - 1; a <= tx + 1; a++) { for (int b = ty - 1; b <= ty + 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 " + tx + "," + ty); } 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(); tx = x; ty = 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 = tx - 1; a <= tx + 1; a++) { for (int b = ty - 1; b <= ty + 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]; } } } } } }
A class you will need:
class Target { public int value; public int sum; public int x; public int y; }
