program Sphinx;
// INGOUFF Christian, 11/01/12 - Version 1.0
uses crt;
type
	matrix = array of array of integer;
	matchar = array of array of char;
	coord = array[1..2] of integer;
	array_coord = array[1..4] of coord;
	array_real = array[1..4] of real;
	array_itg = array[1..4] of integer;

procedure convertGrille(grille : matrix ; var grilchar : matchar ; taille : coord);
// INGOUFF Christian, 11/01/12 - Version 1.0
// Convertit la grille (array of array of integer) en grilchar (array of array of char)
var
	i,j : integer;
begin
	setLength(grilchar,taille[1],taille[2]);
	for i := 0 to taille[1]-1 do
		for j := 0 to taille[2]-1 do
			case grille[i+1,j+1] of
				-42 : grilchar[i,j] := '#'; // Mur
				10 : grilchar[i,j] := '@'; // Porte d'entrée
				0 : grilchar[i,j] := ' '; // Vide
				-1 : grilchar[i,j] := '.'; // Chemin
				15 : grilchar[i,j] := 'O'; // Pion
				42 : grilchar[i,j] := 'X'; // Trésor
			end;
end;
								

procedure affichGrille(grille : matrix; taille : coord);
// INGOUFF Christian, 11/01/12 - Version 1.0
// Affiche la grille de jeu à l'écran
var
	i, j : integer;
	grilchar : matchar;
begin
	convertgrille(grille,grilchar,taille);
	write(' .');
	for i := 1 to taille[1]-1 do
		write('__',i,'___');
	writeln('__',i+1,'__.');
	for j := 0 to taille[2]-1 do
	begin
		write(' ');
		for i := 0 to taille[1]-1 do
			write('|     ');
		writeln('|');
		write(j+1);
		for i := 0 to taille[1]-1 do
			write('|  ',grilchar[i,j],'  ');
		writeln('|');
		write(' ');
		for i := 0 to taille[1]-1 do
			write('|_____');
		writeln('|');
	end;
end;

procedure arrayDirec(var direc : array_coord ; loc : coord);
// INGOUFF Christian, 15/01/12 - Version 1.0
// Retourne les coordonnées des cases environnantes (dans direc)
// (1,1),(1,2) : haut | (2,1),(2,2) : bas | (3,1),(3,2) : gauche | (4,1),(4,2) : droite
begin
	direc[1,1] := loc[1];
	direc[1,2] := loc[2]-1;
	
	direc[2,1] := loc[1];
	direc[2,2] := loc[2]+1;
	
	direc[3,1] := loc[1]-1;
	direc[3,2] := loc[2];
	
	direc[4,1] := loc[1]+1;
	direc[4,2] := loc[2];
end;

function minimum(dist : array_itg):integer;
// INGOUFF Christian, 15/01/12 - Version 1.0
// Retourne le minimum d'un array[1..4] of integer.
var
	i : integer;
begin
	minimum := 1;
	for i := 2 to 4 do
		if (dist[i] < dist[minimum]) then
			minimum := i;
end;
	

procedure eloignement(direc : array_coord ; loc, tresor : coord ; var ordre : array_itg);
// INGOUFF Christian, 15/01/12 - Version 1.0
// Retourne l'ordre : du moins au plus éloigné du trésor
var
	i : integer;
	dist, dist_x, dist_y : array_itg;
begin
	for i := 1 to 4 do
	begin
		dist_x[i] := abs(tresor[1] - direc[i,1]);
		dist_y[i] := abs(tresor[2] - direc[i,2]);
		dist[i] := dist_x[i]*dist_x[i] + dist_y[i]*dist_y[i]; // Distance Pythagore
	end;
	
	for i := 1 to 4 do
	begin
		ordre[i] := minimum(dist); // Assigne le plus petit des 4...
//		writeln('Ordre ',i,' : ',ordre[i]);
		dist[ordre[i]] := 5000; // ...puis exclut cette valeur en la montant.
	end;
end;

procedure verifIni(var grille : matrix ; enter, tresor, taille : coord ; var nb_coups : integer);
// INGOUFF Christian, 15/01/12 - Version 1.0
// Retourne le nombre de coups ainsi que la grille avec le chemin le plus court parcouru.
// Algorithme utilisé : A* (pas forcément optimal)
var
	i, j : integer;
	direc : array_coord;
	ordre : array_itg;
	loc : coord;
begin			
	loc[1] := enter[1];
	loc[2] := enter[2]; // Initialisation de loc au point de départ.
	//writeln('départ = ',loc[1],',',loc[2]);
	for i := 1 to 40 do
	begin
		if (loc[1] = tresor[1]) and (loc[2] = tresor[2]) then break; // Si loc = trésor, on sort.
		grille[loc[1],loc[2]] := -1; // Mise en place du chemin parcouru (sauf départ)
		arrayDirec(direc,loc); // On obtient les coordonnées des cases environnantes
		eloignement(direc,loc,tresor,ordre); // On obtient l'ordre d'éloignement
		j := 1;
		while j <= 4 do
		begin
			if grille[direc[ordre[j],1],direc[ordre[j],2]] >= 0 then // Si la case est libre
			begin
				loc[1] := direc[ordre[j],1]; // On remplace loc par la direction la plus optimale possible
				loc[2] := direc[ordre[j],2];				
				//writeln('loc = ',loc[1],',',loc[2]);
				j := 10;
			end
			else // Si la case n'est pas libre
			begin
				//writeln('Cockblock');
				j := j+1;
			end;
		end;
		if j = 5 then break; // Si aucune case autour n'est disponible
	end;
	
	if (i = 40) or (j = 5) then nb_coups := 666 // Si on tourne en rond ou on est coincés
	else nb_coups := i-1; // Sinon i-1 est le nombre de coups
end;

procedure remplCase(var grille1, grille2 : matrix ; taille : coord ; type_case : integer ; var coord_case : coord);
(* INGOUFF Christian, 11/01/12 *)
var
	valide : boolean;
begin
	repeat
		coord_case[1] := random(taille[1]-1) + 1;
		coord_case[2] := random(taille[1]-1) + 1;
		valide := grille1[coord_case[1],coord_case[2]] = 0;
		if valide then
		begin
			grille1[coord_case[1],coord_case[2]] := type_case;
			grille2[coord_case[1],coord_case[2]] := type_case;
		end
	until valide;
end;

procedure iniGrille(var grille:matrix; taille : coord);
(* Pré-condition : Reçoit un tableau vide de taille définie (non nulle)
   Post-condition : Renvoie la grille remplie
   INGOUFF Christian, 11/01/12 *)
var
	i, j, nb_coups1, nb_coups2, nb_murs : integer;
	tresor, enter, tmp : coord;
	grille1, grille2 : matrix;
begin
	setLength(grille1,taille[1],taille[2]);
	setLength(grille2,taille[1],taille[2]);
	nb_murs := trunc(( 15 / 49 ) * ( (taille[1]-2) * (taille[2]-2) ));
	for i := 0 to taille[1]-1 do
		for j := 0 to taille[2]-1 do
			if (i = 0) or (j = 0) or (i = taille[1]-1) or (j = taille[2]-1) then
			begin
				grille1[i,j] := -42;
				grille2[i,j] := -42;
			end
			else
			begin
				grille1[i,j] := 0;
				grille2[i,j] := 0;
			end;
	remplCase(grille1,grille2,taille,42,tresor); // Trésor = 42
	remplCase(grille1,grille2,taille,10,enter); // Porte d'entrée = 10	
	for i := 1 to nb_murs do
		remplCase(grille1,grille2,taille,-42,tmp); // Mur = -42
	verifIni(grille1,enter,tresor,taille,nb_coups1); // Vérifie du départ à l'arrivée
	verifIni(grille2,tresor,enter,taille,nb_coups2); // Vérifie de l'arrivée au départ
	if ((nb_coups1 = 666) and (nb_coups2 = 666)) then // Si la grille est invalide
		iniGrille(grille,taille) // On recommence
	else if (nb_coups1 < nb_coups2) and (nb_coups1 > 2) then // Sinon on prend le minimum des 2 vérifs
	begin
		for i := 0 to taille[1]-1 do
			for j := 0 to taille[2]-1 do
				grille[i,j] := grille1[i,j];
		grille[enter[1],enter[2]] := 10;
		grille[tresor[1],tresor[2]] := 42;
		writeln('Nombre de coups optimal : ',nb_coups1);
	end
	else if (nb_coups2 > 2) and (nb_coups2 < 666) then
	begin
		for i := 0 to taille[1]-1 do
			for j := 0 to taille[2]-1 do
				grille[i,j] := grille2[i,j];
		grille[enter[1],enter[2]] := 10;
		grille[tresor[1],tresor[2]] := 42;
		writeln('Nombre de coups optimal : ',nb_coups2);
	end
	else iniGrille(grille,taille);
end;	

var
	grille : matrix;
	taille : coord;

begin
	taille[1] := 9;
	taille[2] := 9;
	randomize;
	setLength(grille,taille[1],taille[2]);
	iniGrille(grille,taille);
	taille[1] := 7;
	taille[2] := 7;
	affichGrille(grille,taille);
end.