Problema Labirintului

Cerință:

Se dă un labirint memorat sub forma unei matrice Labirint de elemente 0 și 1, în care unitățile corespund spațiilor pe unde se poate trece, iar zerourile zidurilor. Un șoricel pus într-o anumită căsuță a labirintului ((i_inițial,j_inițial)) va trebui să ajungă într-o altă căsuță a labirintului, unde se află o bucățică de cașcaval ((i_final,j_final)). El se poate mișca doar ortogonal, nu și diagonal.

Indicații de rezolvare:

Pentru a determina toate posibilitățile de a ajunge la cașcaval, fără a trece de mai multe ori
prin acelaşi loc, vom folosi metoda Back-tracking, într-o variantă recursivă, cu unele modificări.
Astfel, nu vom memora drumurile parcurse de șoricel sub forma unui vector x, deoarece nu știm cât de mare poate ajunge acest vector la un moment dat.
Vom folosi, în schimb, o matrice Traseu asociată tablei. Convenim ca Traseu[i,j] să
fie egală cu o valoare numită pas, dacă șoricelul trece la pasul pas pe acolo, în drumul său către cașcaval, respectiv 0, dacă șoricelul nu trece pe acolo.
De asemenea, observăm că șoricelul, dacă se află în poziția (i,j), nu se poate deplasa decât
în patru direcții, sus, jos, stânga și dreapta, în toate aceste direcții doar cu o căsuță (dacă nu este zid!). Astfel, din poziția (i,j), unde a ajuns la pasul pas, va trece într-o poziție nouă
(i_nou,j_nou), la pasul următor, pas+1.
Noile coordonate se obțin din cele vechi prin adăugarea valorilor -1, 0, sau 1, în
conformitate cu cele patru direcții. Acest lucru se va realiza folosind două șiruri speciale de numere, notate prin oriz şi vert.

Implementare:

Cod Sursa PASCAL

 

program ProblemaLabirintului;
const m=8; n=10;
type sir=array[1..4] of ShortInt;
matrice=array[1..m,1..n] of Byte;
const Labirint: matrice
=((0,0,0,0,0,1,0,0,0,0), (0,0,0,1,0,1,0,0,0,0),
(0,0,0,1,1,1,0,0,0,0), (1,1,1,1,0,1,0,0,0,0),
(0,0,0,1,0,1,0,0,0,0), (0,1,1,1,1,1,1,1,0,0),
(1,1,0,0,1,0,0,0,0,0), (0,0,0,0,1,0,0,0,0,0));
const oriz: sir = (-1,0,1,0); vert: sir = (0,1,0,-1);
var Traseu:matrice; i,j,i_initial, j_initial, i_final,j_final: Byte;

procedure Scrie;
var i,j: Integer;
begin
for i:=1 to m do
begin
for j:=1 to n do
Write(Traseu[i,j]:3);
WriteLn
end;
WriteLn
end;

procedure Drum(i,j,pas: Byte);
{procedura recursiva de back-tracking}
var i_nou,j_nou: ShortInt; varianta: Byte;
begin
for varianta:=1 to 4 do
begin
i_nou:=i+oriz[varianta];
j_nou:=j+vert[varianta];
if (i_nou in [1..m]) and (j_nou in [1..n]) then
if (Labirint[i_nou,j_nou]=1) and (Traseu[i_nou,j_nou]=0) then
begin
Traseu[i_nou,j_nou]:=pas;
if (i_nou=i_final) and (j_nou=j_final) then
Scrie
else
Drum(i_nou,j_nou,pas+1);
Traseu[i_nou,j_nou]:=0
end
end
end;

begin
{ se initializeaza matricea Traseu }
for i:=1 to m do
for j:=1 to n do
Traseu[i,j]:=0;
Write(‘Dati pozitia initiala -> ‘);
ReadLn(i_initial, j_initial);
Write(‘Dati pozitia finala -> ‘);
ReadLn(i_final, j_final);
Traseu[i_initial, j_initial]:=1;
WriteLn(‘Solutii : ‘);
Drum(i_initial, j_initial, 2);
ReadLn
end.

Rezultat: