Soluții trimise

Matca cea tânără a decis să părăsească stupul şi să îşi facă propria familie de albine, lucru nu tocmai uşor. Ea, împreună cu albinele sale trebuie să meargă din floare în floare până la marginea plantaţiei. Plantaţia are formă dreptunghiulară cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). În fiecare punct este o floare. Florile sunt codificate cu 0 sau 1, cele codificate cu 0 putând fi ocupate doar de matcă, cele cu valoarea 1 doar de câte o albină. Roiul de albine pleacă de la marginea stângă a plantaţiei (coloana 1) şi trebuie să ajungă în marginea din dreapta (coloana M). La un pas, toate albinele (inclusiv matca) trebuie să se afle pe poziţii consecutive pe aceeaşi coloană. La pasul următor ele se pot deplasa doar pe coloana următoare, dar tot pe poziţii vecine (eventual îşi pot schimba ordinea). Efortul depus pentru deplasarea de pe o coloană pe alta este egal cu diferenţa dintre prima linie ocupată de un membru al roiului de albine (matca sau albină) la pasul anterior şi prima linie ocupată de un membru al roiului albine (matca sau albină) după mutare.

Determinaţi numărul maxim de membri ai roiului de albine (matcă + albine) care pot părăsi stupul pentru a traversa toată plantaţia în scopul formării unei noi familii. Determinaţi, de asemenea efortul total minim cu care matca poate traversa plantaţia cu numărul maxim de albine determinat.