fbpx

Problema labirintului in C++ – Backtracking

0

 

Salutare si bine v-am regasit, astazi vom raspunde unei propuneri primita pe YouTube.

Propunere primita pe YouTube
Propunere primita pe YouTube

 

Enuntul problemei:

Se dă un labirint reprezentat sub forma unei matrici cu n linii şi m coloane, conţinând doar valori 0 şi 1. O succesiune de 1 reprezintă un drum iar o (zero) reprezintă un zid. Dintr-un punct iniţial, a cărui coordonate se citesc, porneşte o persoană. Să se afişeze toate posibilităţile ca acea persoană să ajunga in pozitia finala, ştiind că deplasarea se poate face doar prin valori 1 ale matricei, iar salturile se pot face în stânga, dreapta, jos şi sus.

Ca sa facem un rezumat al problemei, avem:

  • Un fisier de intrare, sa-i zicem „labirint.in” in care scriem urmatoarele valori:
5 8
1 1
3 6
0 1 0 0 0 0 1 0
0 1 1 1 1 1 1 0
0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 0
0 0 0 0 1 0 0 0

Cu urmatoarea semnificatie:

  • 5 8 – dimensiunile matricei (incepem numaratoarea de la 0, dupa cum v-am obisnuit)
  • 1 1 – coordonatele de pornire in matrice
  • 3 6 – coordonatele de sosire in matrice
  • o succesiune de 1, reprezinta o cale libera

De asemenea, in problema mai mentioneaza si faptul ca deplasarea se face doar in 4 directii:

  • Nord: (-1, 0)
  • Est: (0, +1)
  • Sud: (+1, 0)
  • Vest: (0, -1)

Sa trecem la rezolvarea problemei, o sa explic fiecare functie in parte mai jos, si de asemenea o sa fac si o mica animatie, dupa cum v-am obisnuit.

revenim cu edit

Rezolvare problema labirintului:

#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("labirint.in");

const int N_MAX = 2005;
const int M_MAX = 2005;

int N, M;

unsigned int poz_init_X, poz_init_Y;
unsigned int poz_finala_X, poz_finala_Y;

unsigned int matrice[N_MAX][M_MAX];

const int directii = 4;
const int di[directii] = {-1, 0, 1,  0};
const int dj[directii] = {0,  1, 0, -1};

void Citire()
{
    fin >> N >> M;
    fin >> poz_init_X >> poz_init_Y;
    fin >> poz_finala_X >> poz_finala_Y;

    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            fin >> matrice[i][j];
}

bool isOK(int i, int j)
{
    if(i > N || i < 1)
        return false;
    if(j > M || j < 1)
        return false;

    if(matrice[i][j] == 1 || (i == poz_finala_X && j == poz_finala_Y))
        return true;

    if(matrice[i][j] == 0 || matrice[i][j])
        return false;

    return true;
}

void afisare()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
            cout << matrice[i][j] << " ";

        cout << "\n";
    }
    cout << "\n\n";
}

void Rezolvare(int i, int j, int pas)
{
    if(i == poz_finala_X && j == poz_finala_Y)
        afisare();
    else
    {
        for(int k = 0; k < directii; k++)
        {
            int i_vecin = i + di[k];
            int j_vecin = j + dj[k];
            if(isOK(i_vecin, j_vecin))
            {
                matrice[i_vecin][j_vecin] = pas;
                Rezolvare(i_vecin, j_vecin, pas + 1);
                matrice[i_vecin][j_vecin] = 0;
            }
        }
    }
}

int main()
{
    Citire();
    Rezolvare(poz_init_X, poz_init_Y, 2);
    return 0;
}

Functia bool isOK(int i, int j)

  • Primeste ca si parametrii doua numere intregi i si j (sunt numere intregi deoarece pot sa primeasca si -1, altfel le-am fi declarat „unsigned int”)
  • Functia noastra verifica prima oara daca noile coordonate sunt in-afara matricei
  • Mai apoi, accepta toate casutele ce sunt marcate cu 1 (drum disponibil, inca nevizitat) si de-asemenea casuta de final (casuta de final va avea o valoare diferita de 1, in cazul in care se parcurge a doua oara – a trebuit tratat separat acest caz)
  • La final respingem toate casutele de 0 sau casutele diferite de 1 (casute disponibile, dar vizitate)

Functia void Rezolvare(int i, int j, int pas)

  • Este o functie recursiva ce parcurge pe rand vecinii, iar mai apoi se intoarce de unde a plecat – similar algoritmului lui Lee
  • Aceasta functie verifica pe rand toti cei 4 vecini. In cazul in care casuta poate fi vizitata, aceasta functie o viziteaza, iar cand se intoarce din recursivitate marcheaza casuta cu „0” (drum indisponibil)

 

Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More