[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