#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void initBoard(int board[8][8]){
	int i;
	int j;
	int c = 0;
	for(i=0;i<8;i++){
		for(j=0;j<8;j++){
			board[i][j] = c;
			c++;
		}
	}
}

void initAdj(int Adj[64][64]){
	int i;
	int j;
	for(i=0;i<64;i++){
		for(j=0;j<64;j++){
			Adj[i][j] = 0;
		}
	}
}

void availableMove(int x, int y, int board[8][8], int Adj[64][64]){
	int i;
	int j;

	for(i=-2;i<=2;i++){
		for(j=-2;j<=2;j++){
			if(x+i >= 0 && x+i <= 7 && y+j >= 0 && y+j <= 7 && i*j != 0 && (abs(i) == abs(j) + 1 || abs(j) == abs(i) + 1) ){
				Adj[board[x][y]][board[x+i][y+j]] = 1;
			}
		}
	}

}

void calculateAdj(int Adj[64][64], int board[8][8]){
	int x,y;
	for(x=0;x<8;x++){
		for(y=0;y<8;y++){
			availableMove(x,y,board,Adj);
		}
	}

}

void showBoard(int board[8][8]){
	int i;
	int j;
	printf("[*]Printing board : \n");
	for(i=0;i<8;i++){
		for(j=0;j<8;j++){
			printf("%2d ", board[i][j]);
		}
		printf("\n");
	}
	printf("\n\n");
}

void showAdj(int Adj[64][64]){
	int i;
	int j;
	printf("[*]Printing Adj Matrix : \n");
	for(i=0;i<64;i++){
		for(j=0;j<64;j++){
			printf("%d ", Adj[i][j]);
		}
		printf("\n");
	}
	printf("\n\n");
}

void initPoids(int *poids, int depart){
	int i;
	for(i=0;i<64;i++){
		poids[i] = -1;
	}
	poids[depart] = 0;
}
void initTab(int *p){
	int i;
	for(i=0;i<64;i++){
		p[i] = 0;
	}
}

int getMin(int *poids, int *parcours){
	int i;
	int j;
	int min = -1;
	for(i=0;i<63;i++){
		if(poids[i] != -1 && parcours[i] == 0){
			if(min == -1 || min > poids[i]){
				min = poids[i];
				j = i;
			}
		}
	}
	return j;

}

void printTab(int *TAB){
	int i;
	for(i=0;i<64;i++){
		printf("%d:%d ",i,TAB[i]);
	}
	printf("\n\n");
}

int getNextNodeDijkstra(int poids[64], int parcours[64], int antecedent[64], int parent, int Adj[64][64]){
	int i;
	int min;
	parcours[parent] = 1;
	for(i=0;i<64;i++){
		if(Adj[parent][i] == 1){
				int childNode = i;
				if(parcours[childNode] == 0){
					if(poids[parent] + 1 < poids[childNode] || poids[childNode] == -1){
						poids[childNode] = poids[parent]+1;
						antecedent[childNode] = parent;
					}
				}
			}
	}
	min = getMin(poids, parcours);
	return min;
}

void dijkstra(int depart, int arrivee, int Adj[64][64], int board[8][8]){
	int poids[64];
	int parcours[64];
	int antecedent[64];

	initPoids(poids, depart);
	initTab(parcours);
	initPoids(antecedent, depart);

	int next = depart;
	parcours[depart] = 1;
	while(antecedent[arrivee]==-1){
		next = getNextNodeDijkstra(poids,parcours,antecedent,next, Adj);
	}
	showBoard(board);

	int c;
	int i = 1;
	c = arrivee;
	while(c!=depart){
		printf("%d <= ", c);
		c = antecedent[i]
		i++;
	}
}

int main(){
	int board[8][8];
	int Adj[64][64];
	initBoard(board);
	initAdj(Adj);

	int depart = 0;
	int arrivee = 0;
	calculateAdj(Adj, board);
	showBoard(board);
	showAdj(Adj);
	dijkstra(depart,arrivee,Adj,board);
	return 0;
}