Problema labirintului in C++ – Backtracking

Salutare si bine v-am regasit, astazi vom raspunde unei propuneri 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)