
Solução em Pascal do Problema 2
PROGRAMA INCOMPLETO
program backTracking;
const NumMaxElem=?;
NumMaxLin=101;
NumMaxCol=51;
incLin:array [1..4] of -1..1 = (-1,0,1,0);
incCol:array [1..4] of -1..1 = (0,1,0,-1);
type indLinhas=0..NumMaxLin;
indColunas=0..NumMaxCol;
indElem=1..NumMaxElem;
Fila=array[NumMaxElem] of Integer;
Labirinto=array[indLinhas,indColunas] of Integer;
var m, n, i, j, k : Integer;
LQ, CQ, LR, CR : Integer;
inicio, fim, num : Integer;
Lab : Labirinto;
FilaL, FilaC: Fila;
begin
readLn(m);
readLn(n);
for i:=1 to m do begin
for j:=1 to n do
read(lab[i,j]);
readLn
end;
<coloque moldura em lab com -1s>
readLn(LQ,CQ,LR,CR);
{fase de marcação}
lab[LQ,CQ]:=1;
inicio:=0;
fim:=1;
FilaL[1]:=LQ;
FilaC[1]:=CQ;
l:=LQ;
c:=CQ;
while inicio<fim do
begin
inicio:=inicio+1;
l:=FilaL[inicio];
c:=FilaC[inicio];
{retirou primeiro da fila}
num:=lab[l,c]+1;
for k:=1 to 4 do begin
lin:=l+IndLin[k];
col:=c+IndCol[k];
if lab[lin,col]=0
then begin
lab[lin,col]:=num;
fim:=fim+1;
FilaL[fim]:=lin;
FilaC[lin]:=col
{insere no fim da fila}
end
end
end;
{determina caminho mínimo}
l:=LR;
c:=CR;
num:=lab[l,c]-1;
writeLn(l,c);
while num>1 do
begin
k:=1;
while (k<=4) and not achou
begin
lin:=l+IndLin[k];
col:=c+IndCol[k];
if lab[lin,col]=num
then begin
achou:=true;
writeLn(lin,col);
l:=lin;
c:=col
end
else
k:=k+1;
end;
num:=num+1
end;
writeLn(LQ,CQ)
end.
História
da Computação | Listas de
Exercícios | Problemas Resolvidos | macmulti@ime.usp.br