Bombe tomber algorithme

Pólya dit "Si vous ne pouvez pas résoudre un problème, alors il ya un problème plus facile, vous pouvez résoudre: trouver."

L'évidence plus simple problème est le 1-dimensions du problème (lorsque la grille est une seule ligne). Commençons par le plus simple des algorithmes goulûment bombardement de la plus grande cible. Quand est-ce mal?

Donné 1 1 1, l'algorithme glouton est indifférent à la il les premières bombes. Bien sûr, le centre de la cellule est mieux - il de zéros tous les trois cellules à la fois. Ceci suggère un nouvel algorithme A, "bombe à minimiser la somme restante". Quand est-ce que l'algorithme de mal?

Donné 1 1 2 1 1, l'algorithme A est indifférent entre les bombardements de la 2e, 3e ou 4e cellules. Mais les bombardements de la 2ème cellule de quitter 0 0 1 1 1 est mieux que les bombardements de la 3ème cellule de quitter 1 0 1 0 1. Comment résoudre ce problème? Le problème avec les bombardements de la 3ème cellule est qu'il nous laisse travailler à gauche et à travailler pour le droit qui doit être fait séparément.

Comment à propos de "bombe à minimiser la somme restante, mais de maximiser le minimum de la gauche (d'où on a bombardé), en plus du minimum pour le droit". Appelons cet algorithme B. Quand est-ce que l'algorithme de mal?

Edit: Après avoir lu les commentaires, je suis d'accord beaucoup plus intéressante problème serait du à une dimension du problème a changé de sorte que les extrémités se rejoignent. Aimerais voir les progrès sur ce point.

À jour sur la question d'un simple algorithme glouton donne un résultat optimal.

Chute d'Un[0,0] bombes d'Une cellule[1,1], puis déposez Une[1,0] bombes de la cellule A[2,1], et la poursuite de ce processus vers le bas. Pour nettoyer le coin en bas à gauche, déposer max(A[N-1,0], A[N-2,0], A[N-3,0]) bombes à la cellule d'Un[N-2,1]. Ce sera complètement nettoyer les 3 premières colonnes.

Avec la même approche, nettoyage des colonnes 3,4,5, puis les colonnes 6,7,8, etc.

Malheureusement, cela n'aide pas à trouver de solution pour le problème d'origine.

"Gros" problème (sans "nonicreasing" contrainte) peut être prouvée pour être NP-difficile. Voici l'esquisse de la preuve.

Supposons que nous avons un graphe planaire de degré au plus 3. Nous allons trouver le minimum vertex cover de ce graphe. Selon l'article de Wikipedia à ce problème est NP-difficile pour les graphes planaires de degré au plus 3. Cela pourrait être prouvée par la réduction de Planes 3SAT. Et la dureté de la Planaire 3SAT - par la réduction de 3SAT. Ces deux épreuves sont présentées dans les dernières conférences en "Algorithmique Limites Inférieures" par le prof. Erik Demaine (cours 7 et 9).

Si nous nous sommes séparés quelques bords de l'original graphique (graphique de gauche sur le schéma), chacune avec le même nombre de nœuds supplémentaires, le graphe obtenu (graphique de droite sur le schéma) devraient avoir exactement le même minimum vertex cover d'origine pour les sommets. Cette transformation permet d'aligner graphe de sommets à l'arbitraire des positions sur la grille.

Si nous plaçons graphique uniquement des sommets de même les lignes et les colonnes (de telle sorte que deux arêtes incident à un sommet forme un angle aigu), insérer "ceux" là où il y a un bord, et insérer des "zéros" à d'autres positions sur la grille, on peut utiliser n'importe quelle solution pour le problème d'origine pour trouver le minimum vertex cover.

C'est une réponse partielle, j'essaie de trouver une limite inférieure et la limite supérieure, qui pourrait être le nombre de bombes.

En 3x3 et petits conseil d'administration, la solution est trivialement toujours la plus grande cellule numérotée.

Dans les conseils d'administration de plus de 4x4, la première évident limite inférieure correspond à la somme des angles:

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

cependant vous organiser la bombe, il est impossible d'effacer ce 4x4 conseil avec moins de 2+1+6+4=13 bombes.

Il a été mentionné dans d'autres réponses que de placer la bombe sur la deuxième-à-coin pour éliminer le coin n'est jamais pire que de placer la bombe sur le coin lui-même, étant donné que le conseil d'administration:

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

Nous pouvons zéro les coins en plaçant des bombes sur la deuxième-à-coin pour donner un nouveau conseil d'administration:

 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

So far So good. Nous avons besoin de 13 bombes pour effacer les coins.

Maintenant d'observer le nombre de 6, 4, 3 et 2 indiquées ci-dessous:

 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

Il n'y a aucun moyen de bombe deux de ces cellules à l'aide d'une seule bombe, de sorte que le minimum de la bombe a augmenté de 6+4+3+2, donc augmenter le nombre de bombes que nous avons utilisé pour effacer les coins, on obtient que le nombre minimum de bombes requis pour cette carte est devenue 28 bombes. Il est impossible d'effacer cette carte avec les moins de 28 bombes, ce qui est la borne inférieure de cette carte.

Vous pouvez utiliser l'algorithme glouton pour établir une limite supérieure. D'autres réponses ont montré que l'algorithme glouton donne une solution qui utilise 28 bombes. Depuis que nous avons montré précédemment que pas de solution optimale peut avoir moins de 28 bombes, donc 28 bombes est en effet une solution optimale.

Quand gourmand et la méthode pour trouver le minimum lié, je l'ai mentionné ci-dessus ne converge pas bien, je suppose que vous n'avez pas à revenir à la vérification de toutes les combinaisons.

L'algorithme pour trouver la limite inférieure est la suivante:

1. Sur un élément avec le plus grand nombre, le nom de P.
2. Marque toutes les cellules à deux pas de P et de P lui-même comme unpickable.
3. Ajouter P à la minimums liste.
4. Répétez l'étape 1 jusqu'à ce que toutes les cellules sont unpickable.
5. Somme la minimums liste pour obtenir la limite inférieure.

Votre nouveau problème, avec le nondecreasing valeurs entre les lignes, est assez facile à résoudre.

Observer que la colonne de gauche contient le plus grand nombre. Par conséquent, toute solution optimale doit d'abord réduire cette colonne à zéro. Ainsi, nous pouvons effectuer une 1-D bombardement au cours de cette colonne, la réduction de chaque élément à zéro. Nous laissons les bombes tombent sur la deuxième colonne, de sorte qu'ils font le maximum de dégâts. Il y a beaucoup de posts ici à faire avec les 1D cas, je pense que, si je me sens en sécurité dans sauter ce cas. (Si vous voulez me décrire, je peux.). En raison de la diminution de la propriété, les trois colonnes de gauche seront tous réduits à zéro. Mais, nous allons prouvable utiliser un nombre minimum de bombes ici parce que la colonne de gauche doit être remis à zéro.

Maintenant, une fois que la colonne de gauche est mis à zéro, nous venons de couper les trois colonnes de gauche qui sont maintenant remis à zéro et répéter l'opération avec la réduction de la matrice. Cela doit nous donner une solution optimale car à chaque étape, nous utilisons un prouvable nombre minimum de bombes.

Ce n'est d'une largeur de recherche pour le chemin le plus court (une série d'attentats à l'explosif) par le biais de ce "labyrinthe" de postes. Non, je ne peux pas prouver qu'il n'existe pas d'algorithme plus rapide, désolé.

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

Cette gourmande solution semble être correct:

Comme indiqué dans les commentaires, il va échouer en 2D. Mais peut-être que vous pouvez l'améliorer.

Pour 1D:

Si il y a au moins 2 numéros que vous n'avez pas besoin de tirer le plus à gauche parce que le tournage de la deuxième n'est pas pire. Donc tirer à la seconde, alors que la première n'est pas 0, parce que vous avez à faire. Passer à la cellule suivante. N'oubliez pas la dernière cellule.

Code 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])
}
}

Donc pour la 2D:

Nouveau: vous n'avez pas besoin de tirer sur la première ligne (si il y a la seconde). Donc tirer à la seconde. Résoudre 1D tâche de première ligne. (parce que vous devez le faire à null). Aller vers le bas. N'oubliez pas la dernière ligne.

Afin de minimiser le nombre de bombes, nous avons à en maximiser les effets de chaque bombe. Pour arriver à cela, à chaque étape, nous devons sélectionner la meilleure cible. Pour chaque point de sommation et il est huit voisins - peut être utilisée comme un critère d'efficacité de la quantité de bombardement de ce point. Cette offre à peu près de la séquence optimale de bombes.

UPD: il faut aussi prendre le nombre de zéros en compte, parce que bombin est inefficace. En fait, le problème est de minimiser le nombre de hitted zéros. Mais nous ne pouvons pas savoir comment n'importe quelle étape nous rapproche de cet objectif. Je suis d'accord avec l'idée que le problème est NP-complet. Je suggérons une approche gourmande, qui donnera une réponse réel.

Ici est une solution à généraliser les bonnes propriétés des angles.

Supposons que nous pourrions trouver un parfait point de chute pour un champ donné, c'est un meilleur moyen pour diminuer la valeur. Ensuite, pour trouver le nombre minimum de bombes à être abandonné, une première version de l'algorithme pourrait être (le code est à copier-collé à partir d'un rubis de mise en œuvre):

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

Le défi est choose_a_perfect_drop_point. Tout d'abord, définissons ce qu'est un parfait point de chute.

• Un point de chute pour (x, y) diminue la valeur dans (x, y). Il peut aussi diminuer les valeurs d'autres cellules.
• Un point de chute un pour (x, y) est mieux qu'un point de chute b pour (x, y) si elle diminue les valeurs dans une bonne sur-ensemble de cellules qui b diminue.
• Un point de chute maximale si il n'y a pas d'autre meilleur point de chute.
• Deux points de chute pour (x, y) sont équivalent si elles diminuent le même ensemble de cellules.
• Un point de chute pour (x, y) est parfait si c'est équivalent à l'ensemble maximal de points de chute pour (x, y).

Si il y en est un parfait point de chute pour (x, y), vous ne pouvez pas réduire la valeur à (x, y) de manière plus efficace que de larguer une bombe sur l'un des parfaits points de chute pour (x, y).

Un parfait point de chute pour un champ donné est un parfait point de chute pour un de ses cellules.

Voici quelques exemples:

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

Le parfait point de chute pour la cellule (0, 0) (index de base zéro) est (1, 1). Tous les autres points de chute pour (1, 1), c'est-à (0, 0), (0, 1), et (1, 0), la baisse des cellules.

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

Un parfait point de chute pour la cellule (2, 2) (index de base zéro) est (2, 2), et aussi toutes les cellules qui l'entourent (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), et (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

une parfaite points de chute pour la cellule (2, 2) est (3, 1): Il diminue la valeur de (2, 2), et la valeur dans (4, 0). Tous les autres points de chute pour (2, 2) sont pas maximale, car ils diminuent d'une cellule de moins en moins. Le parfait point de chute pour (2, 2) est aussi le parfait point de chute pour (4, 0), et c'est le seul parfait point de chute pour le champ. Elle conduit à la solution parfaite pour ce champ (une bombe de baisse).

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

Il n'est pas parfait point de chute pour (2, 2): les Deux (1, 1) et (1, 3) diminution (2, 2) et une autre cellule (ils sont maximales points de chute pour (2, 2)), mais ils ne sont pas équivalents. Cependant, (1, 1) est un parfait point de chute pour (0, 0), et (1, 3) est un parfait point de chute pour (0, 4).

Avec cette définition parfaite des points de chute et d'un certain ordre de vérifications, j'obtiens le résultat suivant pour l'exemple dans la 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

Cependant, l'algorithme ne fonctionne que si il y a au moins un parfait point de chute après chaque étape. Il est possible de construire des exemples où il n'existe pas de points de chute:

0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

Pour ces cas, nous pouvons modifier l'algorithme de sorte qu'au lieu d'un parfait point de chute, nous avons choisi un système de coordonnées avec un choix minimal maximum de points de chute, puis de calculer le minimum pour chaque choix. Dans le cas ci-dessus, toutes les cellules contenant des valeurs de deux maximal de points de chute. Par exemple, (0, 1) a au maximum les points de chute (1, 1) et (1, 2). Choisir soit l'un, puis calcualting le minimum conduit à ce résultat:

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

Eh bien, supposons que nous nombre les postes du conseil, 1, 2, ..., n x m. Toute séquence de bombe gouttes peut être représenté par une séquence de nombres dans cette série, où le nombre peut répéter. Toutefois, l'effet sur le conseil d'administration est le même, peu importe de quel ordre vous déposez des bombes, si vraiment pas le choix de la bombe gouttes peut être représenté par une liste de n x m, où le premier nombre représente le nombre de bombes larguées sur la position 1, le second nombre représente le nombre de bombes larguées sur la position 2, etc. Appelons cette liste de n x m numéros de la "clé".

Vous pouvez essayer d'abord le calcul de tous les états résultant de l'1 bombe laisser tomber, puis les utiliser pour calculer tous les états résultant de l'2 bombe gouttes, etc jusqu'à ce que vous obtenez tous les zéros. Mais à chaque étape, vous permettrait de mettre en cache les états à l'aide de la clé que j'ai défini ci-dessus, de sorte que vous pouvez utiliser ces résultats dans le calcul de l'étape suivante (une "programmation dynamique" de l'approche).

Mais en fonction de la taille de n, m, et les numéros dans la grille, les besoins en mémoire de cette approche pourrait être excessive. Vous pouvez jeter tous les résultats à la N de la bombe gouttes une fois que vous avez calculé à tous les résultats pour N + 1, donc il y a quelques économies. Et bien sûr, vous pourriez ne cache rien au coût de la faire prendre beaucoup plus -- la programmation dynamique approche des métiers de la mémoire pour la vitesse.

Force Brute !

Je sais que c'est pas efficace, mais même si vous trouvez un algorithme plus rapide, vous pouvez toujours tester à l'encontre de ce résultat pour savoir comment elle est exacte.

Utiliser certains de récursivité, comme ceci:

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

Vous pouvez le rendre plus efficace par la mise en cache, si elle est différente façon conduire à un même résultat, vous ne devriez pas répéter les mêmes étapes.

D'élaborer:

si bombardement de cellules 1,3,5 conduit au même résultat que le bombardement de cellules 5,3,1 , ensuite, vous ne devriez pas refaire toutes les prochaines étapes à nouveau dans les deux cas, 1 seul suffit, vous devez les stocker quelque part tous les états et à l'utilisation de ses résultats.

Un hachage de table stats peut être utilisé pour faire une comparaison rapide.

Voici ma solution.. je ne vais pas l'écrire dans le code mais comme je n'ai pas le temps, mais je crois que cela doit produire un nombre optimal de coups chaque fois, bien que je ne suis pas sûr de savoir comment efficace, il serait à trouver les points à la bombe.

Tout d'abord, comme @Luka Rahne a déclaré dans un des commentaires, l'ordre dans lequel vous bombe n'est pas important, seule la combinaison.

Deuxièmement, comme beaucoup d'autres l'ont dit, le bombardement 1-désactiver la diagonale du coin est optimale, car elle touche plus de points que les coins.

Cela génère la base de ma version de l'algorithme:
Nous pouvons bombe le "1 dans les coins" en premier ou en dernier, il n'a pas d'importance (en théorie)
Nous la bombe à ceux de la première, car elle rend les décisions ultérieures plus facile (dans la pratique)
Nous bombarder le point qui touche le plus de points, tandis que, simultanément, les bombardements les coins.

Nous allons définir les Points De Résistance à être les points de la carte avec le la plupart des non-bombable points + plus grand nombre de 0 autour d'eux

non-bombable points peuvent être définis comme des points qui n'existent pas dans notre portée de la carte, nous sommes à la recherche à.

Je vais également définir des 4 bornes qui va gérer notre portée:
Top=0, Left=0, Bas=k,droite=j.
(valeurs de départ)

Enfin, je vais définir optimale des bombes comme des bombes qui sont tombées sur des points qui sont adjacentes à des points de résistance et sont en contact (1) les plus valorisées point de résistance et (2) le plus grand nombre de points possible.

Concernant le approche il est évident que nous travaillons à partir de l'extérieur. Nous allons être en mesure de travailler avec 4 'bombardiers' en même temps.

Les premiers points de résistance sont évidemment nos coins. Le "hors limite" points ne sont pas bombable (il y a 5 points en dehors de la portée de chaque coin). Afin de nous bombarder les points en diagonale l'un des coins de la première.

Algorithme:

1. Trouver les 4 optimal points bombe.
2. Si une bombe point est de bombarder un point de résistance qui est en contact avec 2 limites (c'est à dire un coin), la bombe jusqu'à ce point est de 0. Sinon, chaque bombe jusqu'à ce que l'un des points de résistance de toucher optimal bombe point est de 0.
3. pour chaque tenue:
   si(somme(lié)==0) avance lié

répétez jusqu'à ce que le HAUT=BAS et de GAUCHE=DROITE

Je vais essayer d'écrire le code plus tard

J'ai 28 se déplace aussi bien. J'ai utilisé deux tests pour le meilleur mouvement suivant: d'abord le déplacement de produire le minimum de la somme pour le conseil d'administration. Deuxièmement, pour l'égalité des sommes, le déménagement, la production de la densité maximale, définie comme:

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

C'est Haskell. "résoudre conseil" montre le moteur de la solution. Vous pouvez jouer le jeu en tapant "principale", puis entrez un point cible, "le meilleur" pour une recommandation, ou "quit" pour quitter.

De SORTIE:

*Principal> résoudre conseil

[(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)

Je ne peux pas penser à un moyen de calculer le nombre réel sans le calcul de la campagne de bombardement à l'aide de ma meilleure heuristique et j'espère obtenir un résultat raisonnable.

Donc ma méthode consiste à calculer un bombardement de mesure du rendement pour chaque cellule, la bombe de la cellule avec la valeur la plus élevée, .... itère le processus jusqu'à ce que j'ai aplati tout. Certains ont préconisé l'aide de simples dommages potentiels (c'est à dire le score de 0 à 9), comme une métrique, mais qui tombe court en battant la valeur élevée des cellules et ne faisant pas usage de dommages se chevauchent. J'avais calculer cell value - sum of all neighbouring cells, réinitialiser aucun résultat positif à 0 et l'utilisation de la valeur absolue de quelque chose de négatif. Intuitivement, cette mesure devrait faire un choix, de maximiser les dégâts de chevauchement sur les cellules avec un nombre élevé à la place de pilonner les personnes directement.

Le code ci-dessous atteint destruction totale de la zone de test dans 28 des bombes (notez que l'utilisation de potentiel de dégâts que métrique rendements 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();
}           
}
}

L'résultant des bombardements modèle est sortie comme suit (les valeurs de champ sur la gauche, métrique sur la droite)

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

fonction d'évaluation, le total de la somme:

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

de la fonction objectif:

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

détruire fonction:

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

objectif de la fonction:

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

linéaire de la maximisation de la fonction:

void solve (int ** matrix, int width, int height)
{
while (!isGoal(matrix,width,height))
{
destroy(matrix,width,height, bestState(matrix,width,height));
}
}

Ce n'est pas optimal, mais peut être optimisé grâce à la recherche d'une meilleure évaluation de la fonction ..

.. mais la réflexion sur ce problème, je pensais que l'un des principaux problèmes est d'obtenir des abandonnés les chiffres dans le milieu de zéros à un certain point, alors j'aimerais prendre une autre approche .. ce qui est de dominer valeurs minimales en zéro, puis essayer de s'échapper de zéros que possible, ce qui conduit en général à une minimisation de peu de valeur existante(s) ou

C'était une réponse à la première question posée. Je n'avais pas remarqué qu'il a changé les paramètres.

Créer une liste de toutes les cibles. Affecter une valeur à la cible sur la base du nombre de valeurs positives impactée par une baisse (lui-même, et tous les voisins). Valeur la plus élevée serait un neuf.

Trier les cibles par le nombre de cibles touchées (Décroissant), avec un second tri décroissant sur la somme de chaque touché la cible.

Larguer une bombe sur la première cible, puis re-calculer les cibles et répétez jusqu'à ce que toutes les valeurs sont égales à zéro.

D'accord, ce n'est pas toujours la plus optimale. Par exemple,

100011
011100
011100
011100
000000
100011

Cette approche permettrait de prendre 5 bombes pour effacer. De manière optimale, même si, vous pouvez le faire en 4. Encore, assez
très proche et il n'y a pas de retour en arrière. Pour la plupart des situations, il sera optimale, ou très proche.

À l'aide de l'origine du problème des chiffres, cette approche permet de résoudre 28 bombes.

L'ajout de code pour illustrer cette approche (à l'aide d'un formulaire avec un bouton):

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

Classe, vous aurez besoin de:

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

Plusieurs réponses jusqu'à présent temps exponentiel, certaines concernent la programmation dynamique. Je doute que si elles sont nécessaires.

Ma solution est O(mn) où m, n sont des dimensions de la planche, S est la somme de tous les nombres entiers. L'idée est plutôt bruteforce: trouver l'emplacement qui peuvent tuer les plus à chaque fois et de mettre fin à 0.

Il donne 28 se déplace pour le conseil donné, et imprime également le conseil d'administration après chaque chute.

Complète, auto-explicatif code:

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