Reação em cadeia (Parte #3)

Esta é uma sequência direta de Reação em cadeia (Parte #2), que era um caso particular mais simples deste desafio (minha sugestão é tentar aquela primeiro).

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

• 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".
• Espaços vazios "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.

Vamos ver alguns exemplos:

[["+", "x"]]

Para o mapa acima, a resposta é 1: para explodir as duas bombas, pode-se escolher a bomba '+'. No entanto, observe que escolher a bomba 'x' não funciona.

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

Para o mapa acima, a resposta é 2: pode-se escolher as duas bombas 'x' da coluna da direita ou as bombas 'x' central e da direita na linha inferior. Nenhuma outra escolha funcionará.

[
  ["x", "x", "x"],
  ["x", "+", "x"],
  ["x", "x", "x"]
]

Para o mapa acima, a resposta é 4: escolha as quatro bombas 'x' nos cantos. Nenhuma outra escolha funciona.

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

Para o mapa acima, a resposta é 1: qualquer bomba, exceto as bombas "x" no canto superior esquerdo e no canto inferior direito, funcionará.

Exemplos

min_bombs_needed([
  ["+", "x"]
]) ➞ 1

min_bombs_needed([
  ["+", "0", "x"],
  ["x", "x", "x"]
]) ➞ 2

min_bombs_needed([
  ["x", "x", "x"],
  ["x", "+", "x"],
  ["x", "x", "x"]
]) ➞ 4

min_bombs_needed([
  ["x", "x", "+"],
  ["+", "0", "+"],
  ["+", "x", "x"]
]) ➞ 1

Notas

• Observe que tanto as bombas "+" quanto as bombas "x" têm um "alcance de explosão" de 1.
• Muitas estratégias que funcionaram na parte #2 falharão nesta.