Backtracking Labirint

Laborator
7/10 (1 vot)
Domeniu: Calculatoare
Conține 4 fișiere: cpp, dat
Pagini : 4 în total
Mărime: 2.23KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Kadlet Francisc
backtracking generalizat

Extras din document

#include <iostream>

#include <fstream>

// Moraru-backtracking generalizat pg.221 problema 51

using namespace std;

int sol[100][2],vecini[5][3],n,m,i,j,x,y,va,mo;

char l[50][50];

FILE f;

void initializari()

{

int i,j;

ifstream f("iepuras.dat");

f>>n>>m;

for(i=1;i<=n;i++)

{

for(j=1;j<=m;j++)

f>>l[i][j];// el. matrici sunt A-liber, M-morcov, V-varza, Z-zid, L-lup//

}

for(i=1;i<=4;i++)

f>>vecini[i][1]>>vecini[i][2];

sol[0][1]=7;//pozitia initiala a iepurasului

sol[0][2]=6;

}

void afis_date()

{

int i,j;

cout<<"datele din fisier sunt:n";

cout<<"n="<<n<<" m="<<m;

cout<<"n matricea labirintului n";

for(i=1;i<=n;i++)

{

for(j=1;j<=m;j++)

cout<<l[i][j]<<" ";

cout<<"n";

}

cout<<"n perechile de vecini sunt: n";

for(i=1;i<=4;i++)

cout<<vecini[i][1]<<" "<<vecini[i][2]<<"n";

}

void tipar (int p)

{

int j,i0,j0;mo=0;va=0;

for(j=0;j<=p;j++)

cout<<"("<<sol[j][1]<<","<<sol[j][2]<<") ";

for(j=0;j<=p;j++)

{ i0=sol[j][1];j0=sol[j][2];

if(l[i0][j0]=='M') mo++;// nr. morcovi culesi de iepure

}

for(j=0;j<=p;j++)

{ i0=sol[j][1];j0=sol[j][2];

if(l[i0][j0]=='V') va++;//nr. varza culeasa de iepure

}

cout<<"n morcovi adunati :"<<mo<<" ";

cout<<"n varza :"<<va;

cout<<"n";

}

int valid(int p)

{

int i,ok,i0,j0; ok=0;

i0=sol[p][1];j0=sol[p][2];

if(l[i0][j0]=='A' || l[i0][j0]=='M' || l[i0][j0]=='V')

{

ok=1;

for(i=0;i<=p-2;i++)

if(sol[p][1]==sol[i][1] && sol[p][2]==sol[i][2]) ok=0;

} return ok;

}

void bktr(int p)

{

int pval;

for(pval=1;pval<=4;pval++)

{

sol[p][1]=sol[p-1][1]+vecini[pval][1];

sol[p][2]=sol[p-1][2]+vecini[pval][2];

if (valid(p))

if(sol[p][1]==1 || sol[p][1]==n || sol[p][2]==1 ||sol[p][2]==n ) tipar(p);

else bktr(p+1);

}

}

int main()

{

initializari();

afis_date();

bktr(1);

return 0;

}

Alții au mai descărcat și

Structuri de Date

1.Enuntul problemei Traseu in labirint Fie un labirint(o retea dreptunghiulara)-cu cellule ocupate (x) si libere (*).Fie un robot (R) in acest...

Metoda Backtracking

Metoda backtracking se utilizeaza pentru rezolvarea unor probleme in care: - se obtin mai multe solutii; -solutia este formata din unul sau mai...

Limbaje Formale

1. Reprezentaţi automatul sub formă de graf. 2. Construiţi gramatica regulată echivalentă cu automatul dat. 3. Este sau nu automatul dat...

Lucrul cu Bazele de Date în Borland C++ Builder

Tema: “Lucrul cu bazele de date in Borland C++ Builder” Scopul: Utilizarea componentei TQuery, posibilitatile crearii si utilizarii cererilor SQL...

WiMAX

Aplicaţiile wireless satisfac cererile utilizatorilor pentru… conexiune simplă: always-on, fără fire, plug-and-play comunicare pentru orice...

Laboratoare la C++

Chişinău 2014 1.Scrieţi un program care calculează suma cifrelor pentru fiecare număr din consecutivitatea de 100 de numere aleatoare. Listing:...

Laborator AFAV - Camtasia Studio

Înregistrarea ecranului În prezent, predarea utilizării calculatoarelor apelează în mod special la cursuri practice şi la cărţi de specialitate....

Grafica pe calculator - Biblioteci grafice 2D

Conditii Varianta 7 ln(1+x) = -∑_(k=0)^∞▒〖(-1)〗^(k+1)*x^2/k , x ∈ (-1,1] De elaborat un program in C++ utilizand Microsoft Foundation Classes...

Ai nevoie de altceva?