Cavalos

cavalos.cpp

#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;
}