Solução de Matheus, comentário por João Guilherme
Para ver o problema original, clique aqui.
A solução é uma aplicação direta da aula sobre flood fill, para vê-la clique aqui. Então o que devemos fazer é ligar dois impérios se um deles atacar o outro. Depois nós passamos por cada império e vemos se ele já foi colorido, se não usamos uma BFS(ou DFS) para pintar todos os seus vizinhos, assim usando um contador para contar o número de componentes conexos.
Segue o código para melhor entendimento.
https://gist.github.com/jogu99/dca1a9162ca0236777e2da8561bd4507
Deixe um comentário