Reação em cadeia (Parte #2)

Esta é uma continuação de Reação em cadeia (Parte #1), com a mesma configuração, mas com uma abordagem diferente.

Assim como na parte anterior, você receberá uma matriz retangular que representa um "mapa" com três tipos de posições:

  • Bombas "+": quando ativadas, sua explosão ativa quaisquer bombas diretamente acima, abaixo, à esquerda ou à direita da bomba "+".
  • Bombas "x": quando ativadas, sua explosão ativa quaisquer bombas colocadas em qualquer uma das quatro direções diagonais ao lado da bomba "x".
  • Posições vazias "0".

O objetivo é simples: dado um mapa, retorne o número mínimo de bombas que precisam ser detonadas para que todas as bombas sejam destruídas pela reação em cadeia.

Vejamos alguns exemplos:

[
  ["+", "+", "+", "0", "+", "+", "+"],
  ["+", "+", "+", "0", "0", "+", "+"]
]

Para o mapa acima, a resposta é 2; para explodir todas as bombas, basta detonar uma bomba "+" no grupo da direita e outra no grupo da esquerda.

[
  ["x", "0", "x"],
  ["x", "x", "x"]
]

Para o mapa acima, a resposta é 3; claramente, detonar as três bombas "x" inferiores é suficiente, e não é possível fazer isso com menos de três bombas.

[
  ["x", "x", "x", "0", "x"],
  ["x", "x", "x", "x", "x"],
  ["x", "x", "x", "0", "x"]
]

Para o mapa acima, a resposta é 3; detonar as três bombas mais à direita na linha do meio resolverá o problema.

Exemplos

minBombsNeeded([
  ["+", "+", "+", "0", "+", "+", "+"],
  ["+", "+", "+", "0", "0", "+", "+"]
]) ➞ 2

minBombsNeeded([
  ["x", "0", "x"],
  ["x", "x", "x"]
]) ➞ 3

minBombsNeeded([
  ["x", "x", "x", "0", "x"],
  ["x", "x", "x", "x", "x"],
  ["x", "x", "x", "0", "x"]
]) ➞ 3

Observações

  • Observe que tanto as bombas "+" quanto as bombas "x" têm um "alcance de explosão" de 1.
  • Para limitar a dificuldade, neste desafio cada mapa terá apenas bombas "+" ou apenas bombas "x". O caso mais desafiador de mapas com bombas "+" e "x" será a parte 3!
  • Descobrir o que fazer é metade da diversão, mas, se você preferir apenas cuidar da programação, há uma dica sobre como abordar este desafio nos comentários.