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;
	array_bool = array of array of boolean;

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 : array of array of char;
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[j,i],'  ');
		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;

procedure extracGrille(var grille : matrix ; grilcoups : matrix ; loc : coord);
// INGOUFF Christian, 16/01/12
// Modélise le chemin obtenu avec algo Dijkstra. Part de trésor (case = nombre de coups) pour aller au départ (case = 0)
var
	direc : array_coord;
	i : integer;
begin
	arrayDirec(direc,loc);
	i := 1;
	if grille[loc[1],loc[2]] <> 10 then
		while i <= 4 do
			if grilcoups[direc[i,1],direc[i,2]] = grilcoups[loc[1],loc[2]] - 1 then
			begin
				grille[loc[1],loc[2]] := -1;
				extracGrille(grille,grilcoups,direc[i]);
				i := 5;
			end
			else
				i := i+1;
end;

procedure bornes(var inf, sup : coord ; enter, taille : coord ; dist : integer);
// Définit inf et sup dans le cadre de "dijkstra"
var
	i : integer;
begin
	for i := 1 to 2 do
	begin
		inf[i] := enter[i]-dist+1;
		if inf[i] < 1 then inf[i] := 1;
		sup[i] := enter[i]+dist+1;
		if sup[i] > taille[i] then sup[i] := taille[i];
	end;
end;

procedure dijkstra(grille : matrix ; var grilcoups : matrix ; tresor, enter, taille : coord ; var nb_coups : integer);
// INGOUFF Christian, 16/01/12
// Test algorithme de Dijkstra (Chemin le plus court optimal, mais assez lourd en opérations)
var
	i, j, k, dist : integer; // dist = Distance par rapport au départ
	loc, inf, sup : coord; // inf et sup = valeurs qui augmenteront selon la distance au départ (recherche en "cercle")
	direc : array_coord;
	valide : boolean;
begin
	dist := 0;
	valide := TRUE;
	while valide and (grilcoups[tresor[1],tresor[2]] = -1) do // Boucle jusqu'à trésor trouvé ou impossible de continuer
	begin
		valide := FALSE;
		bornes(inf,sup,enter,taille,dist);
		for i := inf[1]-1 to sup[1]-1 do
			for j := inf[2]-1 to sup[2]-1 do // On parcourt le tableau d'abord en cercle (avec inf et sup) puis en entier quand dist > taille
				if grilcoups[i,j] = dist then // Si la case correspond à ce tour (dist)
				begin
					loc[1] := i;
					loc[2] := j; // On assigne les coordonnées de cette case à "loc"
					arrayDirec(direc,loc); // On obtient les coordonnées des cases adjacentes
					for k := 1 to 4 do // Pour chaque case adjacente
						if grilcoups[direc[k,1],direc[k,2]] = -1 then // Si la case n'a pas été franchie
						begin
							grilcoups[direc[k,1],direc[k,2]] := dist+1; // La remplir pour le tour suivant (dist+1)
							valide := TRUE; // Indique qu'au moins une case a été remplie pendant ce tour
						end;
				end;
		dist := dist+1;
	end;
	if not valide then nb_coups := -1 // Grille non valide
	else nb_coups := dist;
end;

procedure remplCase(var grille : 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 := grille[coord_case[1],coord_case[2]] = 0;
		if valide then
			grille[coord_case[1],coord_case[2]] := type_case;
	until valide;
end;

procedure remiseZero(var grille, grilcoups : matrix ; taille : coord);
var
	i, j : integer;
begin
	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
				grilcoups[i,j] := -42;
				grille[i,j] := -42;
			end
			else
			begin
				grille[i,j] := 0;
				grilcoups[i,j] := -1;
			end;
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, nb_coups, nb_murs : integer;
	tresor, enter, tmp : coord;
	grilcoups : matrix; // Grille qui va gérer le vérificateur de grilles (nombre de coups)
begin
	setLength(grilcoups,taille[1],taille[2]);
	remiseZero(grille,grilcoups,taille); // Initialise les grilles
	nb_murs := trunc(( 15 / 49 ) * ( (taille[1]-2) * (taille[2]-2) )); // Définit le nombre de murs
	remplCase(grille,taille,42,tresor); // Trésor = 42
	remplCase(grille,taille,10,enter); // Porte d'entrée = 10
	grilcoups[enter[1],enter[2]] := 0; // Point d'entrée pour "dijkstra"
	for i := 1 to nb_murs do
	begin
		remplCase(grille,taille,-42,tmp); // Mur = -42
		grilcoups[tmp[1],tmp[2]] := -42; // Reporte les murs sur la grille pour "dijkstra"
	end;
	dijkstra(grille,grilcoups,tresor,enter,taille,nb_coups);
	if nb_coups < 20 then
		iniGrille(grille,taille)
	else
	begin
		extracGrille(grille,grilcoups,tresor);
		grille[tresor[1],tresor[2]] := 42;
		grille[enter[1],enter[2]] := 10;
		writeln('Nombre de coups optimal : ',nb_coups);
	end;
end;	

var
	grille : matrix;
	taille, taille2 : coord;
begin
	taille[1] := 7;
	taille[2] := 7;
	taille2[1] := taille[1]+2;
	taille2[2] := taille[2]+2;	
	randomize;
	setLength(grille,taille2[1],taille2[2]);
	iniGrille(grille,taille2);
	affichGrille(grille,taille);
end.