8776. Batalha naval

Olá meus amigos nerds, hoje eu peço desculpas a vocês, mas falarei rapidamente sobre um probleminha fácil. Afinal daqui a pouco começa o melhor jogo do ano, a final da Copa do Brasil entre Cruzeiro e Atlético. E como todo bom brasileiro, eu não quero perder essa. Semana que vem, prometo que trago um problema bem mais interessante.

Enquanto esperamos o jogo vamos brincar um pouco de batalha naval? Uma vez que é isso que o problema 8776. Batalha naval nos pede para fazer.  Mais especificamente, o problema nos pede que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determinar o número de navios do outro jogador que foram destruídos.

Solução

Esse problema é bem simples. Para cada posição do mapa, é só verificar se há um navio afundado naquela posição e contar esse navio. Mais algoritmicamente, temos:

cnt = 0
para cada posição do mapa
    if há um navio afundado que ainda não foi contado
        cnt += 1

Para verificar se há um navio afundado em uma posição do mapa é suficiente fazer uma busca em largura a partir daquela posição, ou seja:

vizinhos = fila([posição atual])
afundou = true
while vizinhos não está vazio
    noAtual = vizinhos.top()
    if noAtual não está dentro do mapa
        continue
    if noAtual está intácto
        afundou = false
    else if noAtual recebeu um tiro
        marcar noAtual como visitado
        vizinhos += vizinhos do noAtual 

Implementação