Căutarea unui cuvânt într-o grilă
Ai jucat vreodată „cuvinte încrucișate” sau Boggle? Literele vecine formează un cuvânt dacă le poți lega una de alta, sus, jos, stânga sau dreapta, fără să folosești aceeași celulă de două ori. Problema se rezolvă cu DFS și backtracking: marchezi celula, explorezi, apoi o eliberezi.
Problema
Primești o grilă de litere (o listă de liste) și un cuvânt. Răspunde cu True dacă poți forma cuvântul pornind dintr-o celulă oarecare și mergând de fiecare dată într-o celulă vecină pe orizontală sau verticală. O celulă poate fi folosită o singură dată în același cuvânt.
A B C E S F C S A D E E
Scrie funcția exista_cuvant(grila, cuvant) care returnează True dacă cuvant se poate forma din celule vecine (sus, jos, stânga, dreapta), fiecare celulă folosită cel mult o dată. Marchează celula vizitată și restaureaz-o la întoarcere: ulti…
- Pornește căutarea din fiecare celulă a grilei.
- În funcția recursivă: verifică marginile și litera, marchează celula, încearcă cele 4 direcții, restaurează litera.
- Trebuie să apară: True, True, False, apoi primul rând ['A', 'B', 'C', 'E'].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan