#include <stdio.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <sys/time.h>

int **FazTabuleiroVazio (m, n) {
	int **tabuleiro;  // ponteiro para a matriz
	int   i, j, k;    // variavel auxiliar
	
	// aloca as linhas da matriz 
	tabuleiro = (int **) calloc (m+1, sizeof(int *));
	if (tabuleiro == NULL) {
		printf ("** Erro: Memoria Insuficiente **");
		return (NULL);
	}

	/* aloca as colunas da matriz */
	for ( i = 0; i < m; i++ ) {
		tabuleiro[i] = (int*) calloc (n+1, sizeof(int));
		if (tabuleiro[i] == NULL) {
			printf ("** Erro: Memoria Insuficiente **");
			return (NULL);
		}
	}

	k = 0;
	while (k < m){
		j=0;
		if (k % 2 == 0){
			while (j < n){
				tabuleiro[k][j] = 0;
				j++;
				tabuleiro[k][j] = 4;
				j++;
			}
		k++;
		}
		else{
			while (j < n){
				tabuleiro[k][j] = 4;
				j++;
				tabuleiro[k][j] = 0;
				j++;
			}
		k++;
		}
	}
	return (tabuleiro);
}

void ImprimeTabuleiro(int m, int n, int **tabuleiro){
	int i, j;
	
	for (i=0;i<m;i++){
			for (j=0;j<n;j++){
				printf("%d   ", tabuleiro[i][j]);
			}
		printf("\n\n");
	}
}

int PreencheTabuleiro (int m, int n, int n_casas, int *jogadas, int **tabuleiro){
	int i, j, k;
	
	i = 0;
	j = 0;
	k = 0;
	
	/* Preenche as casas livres do tabuleiro com as informações do vetor jogadas */
	for (k = 0; k <= n_casas; k++){
		for (i = 0; i < m; i++){
			for (j = 0; j < n; j++){
				if (tabuleiro[i][j] == 0){
					tabuleiro[i][j] = jogadas[k];
					k++;
				}
			}
		}
	}
	return (**tabuleiro);
}

int max(int a, int b) {
	if (a > b) return a; //se a é maior que b, a será o valor máximo
	else return b; //do contrário, b será o máximo
}

int verificaJogada (int m, int n, int i, int j, int iComida, int jComida, int **tabuleiro, int visitado[100][100]) {
	// retorna se i está entre 0 e m, se j está entre 0 e n (ou seja, se eles não são limites do tabuleiro)
	// retorna se a posição a ser analizada não foi visitada
	// retorna se a posição do tabuleiro é válida e se a peça a ser comida é 2
	return (i < m && j < n && i >= 0 && j >= 0 && visitado[iComida][jComida] != 1 && tabuleiro[i][j] == 0 && tabuleiro[iComida][jComida] == 2);
}

int contaJogadas(int m, int n, int i, int j, int **tabuleiro, int visitado[100][100]){
	int maximo = 0;
	//verifica se é possível comer para a direita para cima
	if (verificaJogada(m, n, i + 2, j + 2, i + 1, j + 1, tabuleiro, visitado)) {
		//o lugar da peça comida recebe 1 indicando que foi visitado, para que não seja válido comer a mesma peça
		visitado[i + 1][j + 1] = 1;
		/*a função é chamada recursivamente, e maximo recebe o maior numero entre 
		essa chamada e o próprio máximo, é adicionado 1 a contaJogadas pois a jogada anterior
		foi válida e deve ser contada. agora uma nova analise de movimento começa,
		como se a peça 1 estivesse em i+2 e a peça 2 em j-2 */
		maximo = max(1 + contaJogadas(m, n, i + 2, j + 2, tabuleiro, visitado), maximo);
		visitado[i + 1][j + 1] = 0;
	}
	//verifica se é possível comer para a direita para baixo
	if (verificaJogada(m, n, i - 2, j + 2, i - 1, j + 1, tabuleiro, visitado)) {
		visitado[i - 1][j + 1] = 1;
		maximo = max(1 + contaJogadas(m, n, i - 2, j + 2, tabuleiro, visitado), maximo);
		visitado[i - 1][j + 1] = 0;
	}
	//verifica se é possível comer para a esquerda para cima
	if (verificaJogada(m, n, i + 2, j - 2, i + 1, j - 1, tabuleiro, visitado)) {
		visitado[i + 1][j - 1] = 1;
		maximo = max(1 + contaJogadas(m, n, i + 2, j - 2, tabuleiro, visitado), maximo);
		visitado[i + 1][j - 1] = 0;
	}
	//verifica se é possivel comer para a esquerda para baixo
	if (verificaJogada(m, n, i - 2, j - 2, i - 1, j - 1, tabuleiro, visitado)) {
		visitado[i - 1][j - 1] = 1;
		maximo = max(1 + contaJogadas(m, n, i - 2, j - 2, tabuleiro, visitado), maximo);
		visitado[i - 1][j - 1] = 0;
	}
	return maximo;
}

int casasDisponiveis(int *m, int *n){
	return((1 + *m * *n)/2);
}

int **liberar_tabuleiro (int m, int n, int **v){
  int  i;  /* variavel auxiliar */
  if (v == NULL) return (NULL);
  if (m < 1 || n < 1) {  /* verifica parametros recebidos */
     printf ("** Erro: Parametro invalido **\n");
     return (v);
     }
  for (i=0; i<m; i++) free (v[i]); /* libera as linhas da matriz */
  free (v);      /* libera a matriz */
  return (NULL); /* retorna um ponteiro nulo */
}

void funcaogetrusage(struct rusage resources){
	int rc;
	double utime, stime, total_time;
	if((rc = getrusage(RUSAGE_SELF, &resources)) != 0) {
		perror("getrusage failed");
	}
	utime = (double) resources.ru_utime.tv_sec + 1.e-6 * (double) resources.ru_utime.tv_usec;
	stime = (double) resources.ru_stime.tv_sec + 1.e-6 * (double) resources.ru_stime.tv_usec;
	total_time = utime+stime;
	printf("\nTempo de usuario: %.3f\nTempo de sistema: %.3f\nTempo total: %.3f\n",utime, stime, total_time);	
}

double tempo(){
	struct timeval tv;
	gettimeofday(&tv,0);
	return tv.tv_sec + tv.tv_usec/1e6;
}

int funcaogettime(){
	double t1,t2;
	double i;
	t1 = tempo();

	for(i=0;i<30000000;i++);

	t2 = tempo();
	printf("%lf\n",t2-t1);
	return 0;
}

int executaBackTacking(int i, int j, int m, int n, int **tabuleiro, int visitado[100][100], int resultado){
	//para cada i, j será i mod 2 (que vai variar entre 0 e 1), e a cada loop em j, j = j + 2, 
	//o que fará pular as casas inválidas no tabuleiro, sendo:
	// i=0, j=0; i=0, j=2(j % 2 = 0, j = j + 2), i=0, j=4(j % 2 = 0, j = j + 2). Para todo i e j < m, n, respectivamente.
	
	for (i = 0; i < m; i++) {
		for (j = (i % 2); j < n; j = j + 2) {
			if (tabuleiro[i][j] == 1) {
				tabuleiro[i][j] = 0; //"move" a sua peça	
				resultado = max(contaJogadas(m, n, i, j, tabuleiro, visitado), resultado);
				tabuleiro[i][j] = 1;
			}
		}
	}
	return(resultado);
}

int abreEntrada (char *argv[], FILE **arquivo_entrada){
	*arquivo_entrada = fopen(argv[1], "r"); // abre arquivo entrada.txt
	if (arquivo_entrada == NULL){  // Verifica se houve erro na abertura
		printf("\nProblemas na abertura do arquivo\n");
		return(0);
	}
	return(0);
}

int abreSaida (FILE **arquivo_saida){
	*arquivo_saida = fopen("saida.txt", "w"); //abre arquivo saida.txt onde serão salvos os resultados das análises
	if (arquivo_saida == NULL){  // Verifica se houve erro na abertura
		printf("\nProblemas na abertura do arquivo\n");
		return(0);
	}
	return(0);
}

int leEntrada(FILE **arquivo_entrada, int *m, int *n, int *n_casas, int *jogadas){
	int i;
	fscanf(*arquivo_entrada, " %d %d \n ", m, n);
	if (m) printf("\nNumero de linhas : %d \n", *m);
	if (n) printf("\nNumero de colunas : %d \n", *n);
	if (m == 0 && n == 0) return(0);
	
	*n_casas = casasDisponiveis(m, n);
	
	jogadas = (int *) calloc (*n_casas+1, sizeof(int));
	if (jogadas == NULL) {
		printf ("\n Erro: Memoria Insuficiente \n");
		return (0);
	}
	
	for (i=0; i<*n_casas; i++){
		fscanf(*arquivo_entrada, " %d , ", &jogadas[i]);
		printf("jogada %d: %d \n", i, jogadas[i]);
	}
	return(0);
}
	
int main(int argc, char *argv[]) {
	int i = 0, j = 0, m, n, n_casas, resultado;
	int **tabuleiro;
	FILE *arquivo_entrada; //cria variavel do tipo arquivo
	FILE *arquivo_saida; //cria variavel do tipo arquivo
	int jogadas;
	int visitado[100][100];
	struct rusage resources;
	
	abreEntrada(argv, &arquivo_entrada);
	abreSaida(&arquivo_saida);
	
	//enquanto não for o fim do arquivo entrada.txt
	while (!feof(arquivo_entrada)){
		resultado = 0;
		leEntrada(&arquivo_entrada, &m, &n, &n_casas, &jogadas);
		
		tabuleiro = FazTabuleiroVazio (m, n);
		**tabuleiro = PreencheTabuleiro(m, n, n_casas, &jogadas, tabuleiro);
		ImprimeTabuleiro(m, n, tabuleiro);
		resultado = executaBackTacking(i, j, m, n, tabuleiro, visitado, resultado);
		printf("RESULTADO :  %d \n" ,resultado);
        fprintf(arquivo_saida, "%d\n" ,resultado);
		funcaogetrusage(resources);
		funcaogettime();
		tabuleiro = liberar_tabuleiro(m, n, tabuleiro);

	}
	
	fclose(arquivo_entrada);
	fclose(arquivo_saida);
	return 0;
}