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[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;

procedure extracGrille(var grille : matrix ; grilcoups : matrix ; loc : coord);
// INGOUFF Christian, 16/01/12
// Modélise le chemin obtenu avec algo Dijkstra
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 dijkstra(var grille : matrix ; enter, tresor, 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, compt, dist : integer;
	grilcoups : matrix;
	loc : coord;
	direc : array_coord;
begin
	compt := 0;
	setLength(grilcoups,taille[1],taille[2]);
	// Initialisation de la grille des coups
	for i := 0 to taille[1]-1 do
		for j := 0 to taille[2]-1 do
			grilcoups[i,j] := grille[i,j] - 1;
	grilcoups[enter[1],enter[2]] := 0; // Point d'entrée
	grilcoups[tresor[1],tresor[2]] := -1; // Arrivée réglée en libre
	
	// Boucle jusqu'à trésor trouvé ou impossible de continuer
	for dist := 0 to 30 do
	begin
		if (grilcoups[tresor[1],tresor[2]] > 0) then break
		else
			for i := 1 to taille[1]-2 do
				for j := 1 to taille[2]-2 do
				begin					
					compt := compt+1;
					writeln(compt);
					if grilcoups[i,j] = dist then
					begin
						loc[1] := i;
						loc[2] := j;
						arrayDirec(direc,loc);
						for k := 1 to 4 do
							if grilcoups[direc[k,1],direc[k,2]] = -1 then
							begin
								grilcoups[direc[k,1],direc[k,2]] := dist+1;
							end;
					end;
				end;
	end;
	
	if dist = 30 then nb_coups := 666
	else
	begin
		extracGrille(grille,grilcoups,tresor);
		grille[tresor[1],tresor[2]] := 42;
		grille[enter[1],enter[2]] := 10;
		nb_coups := dist;
	end;
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 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_coups, nb_murs : integer;
	tresor, enter, tmp : coord;
begin
	setLength(grille,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
				grille[i,j] := -42
			else
				grille[i,j] := 0;
	remplCase(grille,taille,42,tresor); // Trésor = 42
	remplCase(grille,taille,10,enter); // Porte d'entrée = 10	
	for i := 1 to nb_murs do
		remplCase(grille,taille,-42,tmp); // Mur = -42
	dijkstra(grille,enter,tresor,taille,nb_coups);
	writeln('Nombre de coups optimal : ',nb_coups);
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.