我相信为了减少炸弹的数量，你只需要最大化伤害。 要做到这一点，需要检查具有最强力的区域。因此，您首先分析具有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');

你可以把这个问题表示成整数规划问题。(这只是解决这个问题的一种可能的方法)

有分:

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困难。

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

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

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

输出: *主>解决板 [(4, 4),(3、6),(3),(2,2),(2,2),(4、6)(4、6),(2,6),(2),(4,2)(2,6),(3),(4,3)(2,6)(4,2)(4、6)(4、6),(3、6),(2,6)(2,6)(2、4)(2、4)(2,6),(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)

这将是一个贪婪的方法:

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

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

编辑:

我上面提到的贪心方法，虽然有效，但很可能不能给我们最优的解决方案。所以我想应该添加一些DP的元素。

我想我们可以同意，在任何时候，具有最高“分数”(分数[I][j] =总扣分，如果(I,j)被炸)的位置之一必须被瞄准。从这个假设开始，下面是新的方法:

NumOfBombs(M):(返回所需的最小炸弹数量)

给定一个矩阵M (n X M)，如果M中的所有元素都为0，则返回0。 计算“分数”矩阵M。 设k个不同的位置P1 P2…Pk (1 <= k <= n*m)，为m中得分最高的位置。 return (1 + min(NumOfBombs(M1)， NumOfBombs(M2)，…， NumOfBombs(Mk)) M1, M2,……，Mk是我们轰炸位置P1, P2，…， Pk。

此外，如果我们想在此基础上破坏位置的顺序，我们必须跟踪“min”的结果。

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

向单元格A[1,1]投掷A[0,0]炸弹，然后向单元格A[2,1]投掷A[1,0]炸弹，并继续向下此过程。要清除左下角，向单元格A[n -2,1]投掷max(A[n -1,0]， A[n -2,0]， A[n -3,0])炸弹。这将完全清除前3列。

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

不幸的是，这并不能帮助找到最初问题的解决方案。

“更大”的问题(没有“非增加”约束)可能被证明是np困难的。这是证明的草图。

假设我们有一个度为3的平面图形。我们来求这个图的最小顶点覆盖。根据维基百科的文章，这个问题对于3次以下的平面图形是np困难的。这可以通过平面3SAT的简化来证明。平面3SAT的硬度由3SAT降低而成。这两个证明都在Erik Demaine教授最近的“算法下界”讲座(第7和第9讲)中提出。

如果我们分割原始图的一些边(图中左边的图)，每条边都有偶数个额外的节点，结果图(图中右边的图)应该对原始顶点具有完全相同的最小顶点覆盖。这样的转换允许将图顶点对齐到网格上的任意位置。

如果我们将图顶点只放置在偶数行和列上(这样就不会有两条边与一个顶点形成锐角)，在有边的地方插入“1”，在其他网格位置插入“0”，我们可以使用原始问题的任何解决方案来找到最小顶点覆盖。

这是另一个想法:

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

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

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

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

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

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

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