Jump to content
Forum Roportal
ThunderCrackR

Sfat: problemă backtracking matrice de caractere

Rate this topic

Recommended Posts

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!

Edited by ThunderCrackR

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×