#4742
Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n
linii și m
coloane, care definesc n*m
sectoare. În fiecare sector se află o comoară ascunsă de Ali Baba. Se cunoaște valoarea în galbeni a fiecărei comori.
Un călător trebuie să traverseze deșertul de la Vest spre Est, trecând dintr-un sector în altul, astfel: din sectorul (i j)
se poate ajunge în unul din sectoarele (i-1,j+1)
, (i,j+1)
sau (i+1,j+1)
, dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul colectează comoara din acel sector.
Determinați valoarea totală maximă a comorilor pe care le poate colecta călătorul la traversarea deșertului, știind că pleacă din orice sector al coloanei 1
(Vest) și se oprește în orice sector al coloanei m
(Est), cu respectarea condițiilor de mai sus.