Planul unui teren aurife de forma dreptunghilara cu dimesiunile n*m este format din zone patratice cu latura1. In zona sin coltul nord-west se afla un robot. Din zona cu coordonate (i,j) robotul poate extrage cel mult a(ij) grame de aur.Din considerente tehnologice pe teren exista restrictii de deplasare : la fiecare pas robotul poate misca din zona curenta numai in una din zonele vecine-cea din est (in drapta) sau cea din sud (in jos ). Elaborati un program care determina cantitatea maxima de aur Cmax care poate fi extrasa de robot. C++ HELP
Răspunsuri la întrebare
Program C++ :
#include <iostream>
using namespace std;
struct Teren {
int n;
int m;
int** matrice;
};
struct Robotel {
int i=0;
int j=0;
int cantitate_aur=0;
};
int** alocare_matrice(int nLinii, int nColoane) {
int** p = new int* [nLinii];
for (int index = 0; index < nLinii; index++)
p[index] = new int[nColoane];
return p;
}
Teren citire_date_teren() {
Teren t;
cout << "Numarul de linii : ", cin >> t.n;
cout << "Numarul de coloane : ", cin >> t.m;
t.matrice = alocare_matrice(t.n, t.m);
cout << "Introduceti elementele matricei : \n";
for (int linie = 0; linie < t.n; linie++) {
for (int coloana = 0; coloana < t.m; coloana++) {
cin >> t.matrice[linie][coloana];
}
}
return t;
}
int backtracking(const Teren &t, Robotel r) {
//Actualizeaza valoarea gasita de robot
r.cantitate_aur += t.matrice[r.i][r.j];
//Ai ajuns in coltul din dreapta jos
if (r.i == t.n - 1 && r.j == t.m - 1) return r.cantitate_aur;
//Pregateste robotelul pentru expeditiile imediat urmatoare
Robotel est = r;
Robotel sud = r;
//Daca robotelul poate merge in est
if (sud.i < t.n-1) {
sud.i++;
sud.cantitate_aur = backtracking(t, sud);
}
//Daca robotelul poate merge in sud
if (est.j < t.m - 1) {
est.j++;
est.cantitate_aur = backtracking(t, est);
}
//Returneaza maximul dintre castigul expeditiilor din est si celor din sud
return max(sud.cantitate_aur, est.cantitate_aur);
}
int main() {
int n, m;
Teren t = citire_date_teren();
Robotel r;
int Cmax = backtracking(t, r);
cout << "Cantitate maxima aur " << Cmax;
}
Ai testarea programului si fisier .txt cu codul atasate.
