fbpx

Problema calului in C++ – Backtracking

1

Problema primita pe pagina de Facebook
Problema primita pe pagina de Facebook

Salutare si bine v-am regasit, astazi vom raspunde unei probleme primite pe pagina noastra de Facebook.

Enuntul problemei:

Se da o tabla de sah cu dimensiunea NxN. Un cal se gaseste in linia 1 si coloana 1. Gasiti un sir de mutari ale calului astfel incat acesta sa acopere intreaga tabla de sah fara a trece printr-o casuta de 2 ori.

Acesta problema este foarte asemanatoare cu problema labirintului. Doar ca difera ceva, de data asta nu ne mai deplasam nord – sud – est – vest, ne deplasam cum se deplaseaza calul pe tabla de sah.

Toate mutarile posibile
Toate mutarile posibile

Am incercat mai sus sa desenez toate mutarile posibile pe care le poate face calutul nostru. Daca transpunem poza in doi vectori de directii, rezultatul este urmatorul:

Functia bool isOK(int x, int y)

  • Primeste ca si parametrii doua numere intregi x si y (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
  • De asemenea, casuta este respinsa daca a mai fost vizitata in trecut (valoarea mai mare ca 1)

Functia bool isFull()

  • Verifica daca toate casutele sunt diferite de 0
  • Cele doua for-uri pot fi inlocuite cu o conditie de genu
    • if(numar_mutare_curenta >= n)
      return false;

Functia void Rezolvare(int x, int y)

  • 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 8 vecini. In cazul in care casuta poate fi vizitata, aceasta functie o viziteaza, iar cand se intoarce din recursivitate marcheaza casuta cu „0” (casuta nevizitata)

Daca doriti sa generati doar o solutie, decomentati linia cu exit(1);

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