⛰️ Problema
Avem un teren de N×M parcele, fiecare cu o înălțime cunoscută. O bilă pornește dintr-o parcelă interioară și se poate deplasa la oricare parcelă vecină (sus/jos/stânga/dreapta) care are înălțime strict mai mică.
Scopul: găsim toate căile posibile prin care bila poate ajunge la marginea terenului.
🔁 Abordarea BKT
La fiecare pas, bila încearcă toate cele 8 direcții (inclusiv diagonale). O mișcare e validă dacă celula vecină există, nu a mai fost vizitată în calea curentă și are înălțime mai mică. Dacă bila ajunge la margine — soluție găsită!
Deoarece înălțimile sunt strict descrescătoare pe orice cale, nu pot exista cicluri — vizitarea nu e necesară.
💻 Cod C++ — Bila pe Teren BKT
💻 Cod C++
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("bila.in");
struct comp {int l,c;};
comp x[50], depl[10]={ {0,0} , {-1,0} ,{-1,1} ,{0,1} ,{1,1},{1,0},{1,-1}, {0,-1},{-1,-1} };
int tab[30][30] , n , l0 , c0 , sol=0, d[10];
void CITIRE()
{
int i,j;
f>>n;
for(i=1;i<=n;i++) for(j=1;j<=n;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]<8) 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)
{
if(tab[x[k].l][x[k].c]>=tab[x[k-1].l][x[k-1].c]) return 0;
return 1;
}
int SOLUTIE (int k)
{
if((x[k].l==1)||(x[k].l==n)||(x[k].c==1)||(x[k].c==n)) return 1;
else return 0;
}
void TIPAR(int k)
{
int i; sol++;
for(i=1;i<=k;i++)
cout<<x[i].l<<"-"<<x[i].c<<" ";
cout<<endl<<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()
{
int i,j;
cout<<"------------------------------"<<endl<<endl;
cout<<"Problema bilei"<<endl<<endl;
cout<<"------------------------------"<<endl<<endl;
CITIRE();
cout<<"Configuratia terenului:"<<endl<<endl;
for(i=1;i<=n;i++) { for(j=1;j<=n;j++) cout<<tab[i][j]<<" "; cout<<endl;}
cout<<endl;
cout<<"------------------------------"<<endl<<endl;
cout<<"Solutii posibile pentru configuratia data: "<<endl<<endl;
BCKG();
cout<<"------------------------------"<<endl<<endl;
if(sol==0) cout<<"Nu exista solutii pentru aceasta configuratie.";
else cout<<"S-au generat "<<sol<<" de solutii."<<endl;
}