Caută în comunitate
Afișez rezultate pentru tagurile 'backtracking'
Găsit 1 rezultat
-
Salut! Am nevoie de sfatul vostru în înțelegerea textului unui enunț, pentru că, aparent, modurile prin care am încercat să mi-l explic eu însumi nu m-au dus la rezultatul precizat pentru exemplu. Enunț: „Fie o matrice n*m, în fiecare celulă având câte un caracter. Citim de la tastatură un șir de caractere. Câte soluții de concatenare a caracterelor, plimbându-ne pe orizontală și/sau pe verticală, fără a trece de 2 ori prin aceeași celula, găsim astfel încât șirul rezultat să fie identic cu șirul citit?” Exemplu: n=4, m=5, șirul s='MAMA' Matricea: O a A M A G m M a M F M A M A X P I A M Răspuns: Rezultă 7 (șapte) soluții. Eu am scris codul în C++, bazându-mă pe problema labirintului backtracking, ținând cont de cele 4 direcții, iar problema rulează (credeam) coret: pentru fiecare 'M' verifică toate posibilitățile din jurul său de a forma, prin alipirea cu elemente succesive, cuvântul 'MAMA'. Problema este că, pentru exemplul dat, există 21 de moduri de formare a cuvântului 'MAMA', luând toate posibilitățile pentru fiecare M, fără a trece într-o parcurgere prin aceeași celulă (numai pentru M(2,3) există 3 moduri de formare a cuvântului!!!). Prin urmare, ce îmi scapă mie din enunț, ce condiție mai este necesară pentru a fi redus numărul de soluții la numai 7? Mulțumesc anticipat!
