Se citesc doua numere naturale n si m, o grila de n linii si m coloane cu litere mari, si un cuvant. Determinati, folosind metoda Backtracking, daca cuvantul se poate forma pornind de la o celula a grilei si deplasandu-va, la fiecare pas, la o celula adiacenta (sus, jos, stanga sau dreapta), fara a folosi aceeasi celula de doua ori, astfel incat literele intalnite, in ordine, sa formeze exact cuvantul dat.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza n linii, fiecare cu un sir de m litere mari (fara spatii). Pe ultima linie se citeste cuvantul cautat.
- Date de iesire
- Se afiseaza DA daca cuvantul poate fi format, respectiv NU in caz contrar.
- Restrictii
- 1 <= n, m <= 10, 1 <= lungimea cuvantului <= 12
Exemple
Exemplul 1
Intrare
3 4 ABCE SFCS ADEE ABCCED
Iesire
DA
Exemplul 2
Intrare
3 4 ABCE SFCS ADEE SEE
Iesire
DA