Olá, estamos aqui de novo para resolver mais problemas! Hoje vamos falar de batalha naval e nos divertir um pouco contando quantos navios conseguimos afundar nesse conhecido jogo, já que é isso que o problema 8776. Batalha naval nos pede.
Modelagem
Mais especificamente, esse problema nos pede que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determine o número de navios do outro jogador que foram destruídos.
A entrada do problema já nos dá uma boa ideia de como resolvê-lo, basta armazenar o tabuleiro em uma matriz e contar quantos navios foram afundados. Cada posição da matriz pode ser de três tipos: água, navio intacto ou navio avariado por um disparo. Observe que não precisamos armazenar a informação sobre os tiros que acertaram a água.
A restrição de que dois navios não podem ter arestas em comum nos permite aplicar uma busca em largura ao tabuleiro e ir contando quantos navios foram afundados. Não vou explicar, aqui, o que é uma busca em largura já que esse assunto é extensamente abordado em qualquer estudo sobre grafos. Veja que estou apenas pegando emprestada a ideia da busca em largura, mas não estou modelando o problema usando grafos.
Complexidade
Dado um tabuleiro de N x M nossa solução avalia cada posição da matriz uma vez, assim sendo nossa solução é O(N*M).
Implementação
Abaixo uma implementação em c++ do problema. Infelismente, não estou muito inspirado para falar sobre ela já que, como você deve ter visto, o problema é bem simples.
Nenhum comentário:
Postar um comentário