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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <algorithm> | |
| using namespace std; | |
| #define MAXN 1010 | |
| int m, n, cor[MAXN][MAXN], cor1, cor2, resp; | |
| // DFS para bipartirmos o tabuleiro | |
| void dfs(int i, int j){ | |
| // suponha que um cavalo está na casa i, j do tabuleiro | |
| int i_=i+1, j_=j+2; | |
| // para cada casa que ele pode atacar que ainda não tenha cor | |
| if(i_>=1 and i_<=n and j_>=1 and j_<=m and !cor[i_][j_]){ | |
| // a colorimos de uma cor oposta à da casa original | |
| // lembrando de atualizar as quantidades de casas de cada cor | |
| if(cor[i][j]==1){ | |
| cor[i_][j_]=2; | |
| cor2++; | |
| } | |
| else{ | |
| cor[i_][j_]=1; | |
| cor1++; | |
| } | |
| // e chamo a DFS para essa casa | |
| dfs(i_,j_); | |
| } | |
| // repito o processo com cada casa que o cavalo alcança | |
| i_=i+1, j_=j-2; | |
| if(i_>=1 and i_<=n and j_>=1 and j_<=m and !cor[i_][j_]){ | |
| if(cor[i][j]==1){ | |
| cor[i_][j_]=2; | |
| cor2++; | |
| } | |
| else{ | |
| cor[i_][j_]=1; | |
| cor1++; | |
| } | |
| dfs(i_,j_); | |
| } | |
| i_=i-1, j_=j+2; | |
| if(i_>=1 and i_<=n and j_>=1 and j_<=m and !cor[i_][j_]){ | |
| if(cor[i][j]==1){ | |
| cor[i_][j_]=2; | |
| cor2++; | |
| } | |
| else{ | |
| cor[i_][j_]=1; | |
| cor1++; | |
| } | |
| dfs(i_,j_); | |
| } | |
| i_=i-1, j_=j-2; | |
| if(i_>=1 and i_<=n and j_>=1 and j_<=m and !cor[i_][j_]){ | |
| if(cor[i][j]==1){ | |
| cor[i_][j_]=2; | |
| cor2++; | |
| } | |
| else{ | |
| cor[i_][j_]=1; | |
| cor1++; | |
| } | |
| dfs(i_,j_); | |
| } | |
| i_=i+2, j_=j+1; | |
| if(i_>=1 and i_<=n and j_>=1 and j_<=m and !cor[i_][j_]){ | |
| if(cor[i][j]==1){ | |
| cor[i_][j_]=2; | |
| cor2++; | |
| } | |
| else{ | |
| cor[i_][j_]=1; | |
| cor1++; | |
| } | |
| dfs(i_,j_); | |
| } | |
| i_=i+2, j_=j-1; | |
| if(i_>=1 and i_<=n and j_>=1 and j_<=m and !cor[i_][j_]){ | |
| if(cor[i][j]==1){ | |
| cor[i_][j_]=2; | |
| cor2++; | |
| } | |
| else{ | |
| cor[i_][j_]=1; | |
| cor1++; | |
| } | |
| dfs(i_,j_); | |
| } | |
| i_=i-2, j_=j+1; | |
| if(i_>=1 and i_<=n and j_>=1 and j_<=m and !cor[i_][j_]){ | |
| if(cor[i][j]==1){ | |
| cor[i_][j_]=2; | |
| cor2++; | |
| } | |
| else{ | |
| cor[i_][j_]=1; | |
| cor1++; | |
| } | |
| dfs(i_,j_); | |
| } | |
| i_=i-2, j_=j-1; | |
| if(i_>=1 and i_<=n and j_>=1 and j_<=m and !cor[i_][j_]){ | |
| if(cor[i][j]==1){ | |
| cor[i_][j_]=2; | |
| cor2++; | |
| } | |
| else{ | |
| cor[i_][j_]=1; | |
| cor1++; | |
| } | |
| dfs(i_,j_); | |
| } | |
| } | |
| int main(){ | |
| // leio os valores de m e n | |
| scanf("%d %d", &m, &n); | |
| // para cada casa do tabuleiro | |
| for(int i=1; i<=n; i++) | |
| for(int j=1; j<=m; j++){ | |
| // se ela já tiver sido colorida, continuo | |
| if(cor[i][j]) continue; | |
| // caso contrário, a pinto da cor 1 | |
| cor[i][j]=cor1=1; | |
| // chamo a DFS nela | |
| dfs(i,j); | |
| // e adicioniono a resp a quantidade de casas pintadas | |
| // da cor que mais apareceu na bipartição do grafo | |
| resp+=max(cor1,cor2); | |
| // e zero as quantidades de casas de cada cor | |
| // para as próximas bipartições | |
| cor1=cor2=0; | |
| } | |
| // por fim, imprimo o valor salvo em resp | |
| printf("%d\n", resp); | |
| return 0; | |
| } |