🌿 Problema
Avem un labirint de N×M celule. Fiecare celulă este fie perete (0), fie drum (1). Șoricelul pornește dintr-o celulă interioară și trebuie să ajungă la marginea labirintului — orice celulă de bordură care este drum este o ieșire validă.
Scopul: găsim toate căile posibile spre ieșire, fără a trece de două ori prin aceeași celulă.
🔁 Abordarea BKT
La fiecare pas, șoricelul încearcă cele 4 direcții (sus, jos, stânga, dreapta). O mișcare e validă dacă celula vecină există, nu este perete și nu a mai fost vizitată în calea curentă. Dacă ajunge la margine — soluție!
Backtrack-ul marchează celula curentă ca neexplorat și se întoarce la celula anterioară pentru a încerca alte direcții.
💻 Cod C++ — Labirint BKT
💻 Cod C++
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("lab.in");
struct comp {int l,c;};
comp x[50], depl[5]={ {0,0} , {-1,0} ,{0,1} ,{1,0} ,{0,-1} };
int tab[30][30] , n ,m , l0 , c0 , sol, d[5];
void CITIRE()
{
int i,j;
f>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>tab[i][j];
f>>l0>>c0;
x[1].l=l0;
x[1].c=c0;
}
void INIT(int k) { d[k]=0; }
int EXISTA(int k)
{
if(d[k]<4) return 1;
else return 0;
}
void VALPOS(int k)
{
x[k].l=x[k-1].l+depl[d[k]].l;
x[k].c=x[k-1].c+depl[d[k]].c;
}
int VALID(int k)
{
int i;
for(i=1;i<k;i++)
if((x[k].l==x[i].l)&&(x[k].c==x[i].c)) return 0;
if(tab[x[k].l][x[k].c]==0) return 0;
return 1;
}
int SOLUTIE(int k)
{
if((x[k].l==1)||(x[k].l==n)||(x[k].c==1)||(x[k].c==m)) return 1;
else return 0;
}
void TIPAR(int k)
{
int i; sol++;
cout<<"Solutia "<<sol<<":"<<endl;
for(i=1;i<=k;i++)
cout<<x[i].l<<" "<<x[i].c<<endl;
cout<<endl;
}
void BCKG()
{
int k=2;
INIT(k);
while (k>1)
if(EXISTA(k)) {
d[k]++;
VALPOS(k);
if(VALID(k)) if(SOLUTIE(k)) TIPAR(k);
else {k++; INIT(k);}
}
else k--;
}
int main()
{
CITIRE();
BCKG();
}