[C++, programare dinamică] Problemă – algoritmul lui Lee (c) – afișarea tuturor drumurilor optime

Introducere în problema labirintului aici.

Enunț

c) Modificați funcția de afișare a drumului astfel încât să afișeze toate drumurile minime existente.

Explicație

Cum se cere modificarea funcției existente, nu crearea unei noi funcții, există opțiunea de a transforma funcția din recursivă în nerecursivă și de a folosi un arbore (fiecare nod al arborelui are cel mult 4 descendenți direcți, în structura de nod a arborelui se rețin coordonatele x – implicit -1, y – implicit -1 și părintele – implicit NULL).

Funcția recursivă de aflare a unui singur drum optim este următoarea:

void drum_unic(int D[maxn][maxn], int N, int x, int y,
ofstream &out)
{
if (D[x][y] == 0)
{
out
<< 2 5\n; // aici se înlocuiește „2 5” cu poziția de pornire
return;
}

for (int i = 0; i < 4; ++i)
{
int newx = x + dx[i];
int newy = y + dy[i];

if (valid(N, newx, newy))
if (D[newx][newy] == D[x][y] 1)
{ drum_unic(D, N, newx, newy, out);
break;
}
}

out << x << ‘ ‘ << y << \n;
}

Funcția nerecursivă de aflare a unui singur drum optim este următoarea:

void drum_unic_nerec(int D[maxn][maxn],
int N, ofstream &out)
{
queue<pair<int, int>> Q;

Q.push(make_pair(2, 5)); // aici se înlocuiește (2, 5) cu poziția de pornire

while (!Q.empty())
{
pair<int, int> p = Q.front();
Q
.pop();

out << p.first << ‘ ‘ << p.second << endl;

for (int i = 0; i < 4; ++i)
{
int newx = p.first + dx[i];
int newy = p.second + dy[i];

if (valid(N, newx, newy))
if (D[newx][newy] == D[p.first][p.second] + 1)
{
Q
.push(make_pair(newx, newy));
break;
}
}
}
}

Funcția nerecursivă de afișare a tuturor drumurilor optime este următoarea:

void toate_drumurile_nerec(int D[maxn][maxn],
int N, ofstream &out)
{
Nod *nod = new Nod;
nod->x = 2; // aici se înlocuiește (2, 5) cu poziția de pornire
nod->y = 5;

queue<Nod *> Q;
Q.push(nod);

while (!Q.empty())
{
Nod *p = Q.front();
Q.pop();

for (int i = 0; i < 4; ++i)
{
int newx = p->x + dx[i];
int newy = p->y + dy[i];

if (valid(N, newx, newy))
if (D[newx][newy] == D[p->x][p->y] + 1)
{
Nod *v = new Nod;
v->x = newx;
v->y = newy;
v->parinte = p;

if (p->copil1 == NULL)
{
p->copil1 = v;
}
else if (p->copil2 == NULL)
{
p->copil2 = v;
}
else if (p->copil3 == NULL)
{
p->copil3 = v;
}
else if (p->copil4 == NULL)
{
p->copil4 = v;
}
else
{
// eroare
}

Q.push(v);
}
}
}

// afisare:

stack<Nod *> s;
s.push(nod);

// parcurgere in adancime pentru gasirea tuturor frunzelor
while (!s.empty())
{
Nod *n = s.top();
s.pop();

bool are_descendenti_directi = false;
if (n->copil1 != NULL)
{
s.push(n->copil1);
are_descendenti_directi = true;
}
if (n->copil2 != NULL)
{
s.push(n->copil2);
are_descendenti_directi = true;
}
if (n->copil3 != NULL)
{
s.push(n->copil3);
are_descendenti_directi = true;
}
if (n->copil4 != NULL)
{
s.push(n->copil4);
are_descendenti_directi = true;
}

// daca este frunza (nu are descendenti directi)
if (!are_descendenti_directi)
{
afiseaza_drum_radacina_frunza(n, out);
// sau: afiseaza_drum_frunza_radacina(n);
}
}
}


Această funcție folosește următoarea structură:

struct Nod
{
Nod *parinte = NULL;
Nod *copil1 = NULL;
Nod *copil2 = NULL;
Nod *copil3 = NULL;
Nod *copil4 = NULL;
int x = -1,
y = -1;
};

și în plus, următoarele două funcții de afișare:

// afiseaza drumul de la o frunza la radacina
void afiseaza_drum_frunza_radacina(Nod *f, ofstream &out)
{
while (f != NULL)
{
out << f->x << " " << f->y << endl;

f = f->parinte;
}
out << endl;
}

// afiseaza drumul de la radacina la o frunza
void afiseaza_drum_radacina_frunza(Nod *f, ofstream &out)
{
stack<Nod *> s;

while (f != NULL)
{
s.push(f);

f = f->parinte;
}

while (!s.empty())
{
f = s.top();
s.pop();

out << f->x << " " << f->y << endl;
}
out << endl;
}

In rest codul este la fel ca in articolul de la link-ul de la începutul acestui articol. In funcția main se face apelul:

toate_drumurile_nerec(D, N, out);


după deschiderea fișierului lee.out care se face după apelul la funcția Lee.

Exemplu

Pentru datele de intrare:

5
1 1 1 1 1
1 0 0 0 0
1 0 0 1 1
1 0 0 1 1
1 0 1 1 1

datele de ieșire sunt:

6

2 5
2 4
2 3
2 2
3 2
4 2
5 2

2 5
2 4
2 3
3 3
3 2
4 2
5 2

2 5
2 4
2 3
3 3
4 3
4 2
5 2

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Fotografie Google

Comentezi folosind contul tău Google. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

%d blogeri au apreciat: