Solução Cavalos

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Vejamos o tabuleiro como um grafo em que as casas são vértices, e dois vértices estão ligados se as casas que eles representam são casas em que um cavalo pode ir, em um movimento, de uma para a outra.

Imagine agora uma componente conexa desse grafo. Note que ela é bipartida, visto que casas pretas só se ligam a casas brancas (pois um cavalo sempre muda a cor da casa em que está ao realizar um movimento). Desse modo, nesta componente, temos duas opções: ou colocamos cavalos em todas as casas preta ou em todas as casas brancas, basta escolhermos as que aparecem em maior quantidade!

De maneira geral, para cada componente conexa do grafo, vamos biparti-la em dois subconjuntos e adicionar à resposta o  número de vértices que aparecem no maior conjunto, pois podemos colocar um cavalo em cada casa dessas. Note que, por definição, dois cavalos do mesmo conjunto não se atacam (pois o grafo e bipartido!).

O algoritmo de bipartição de um grafo é simples: basta usarmos uma DFS. Quando chamamos a DFS para um determinado vértice, pintamos cada um de seus vizinhos da cor diferente da sua e chamamos a DFS para cada um deles. Segue o código para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: