Fişierul intrare/ieşire:drum6.in, drum6.outSursăAlgoritmiada 2015, Runda 2
AutorMihai CalanceaAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Drum6

Cu toţii ştim cât de mult îi place lui Trăncănici să vorbească. Atât de mult, încât cu o seară înainte a avut un vis foarte ciudat...

Acesta se afla în căsuţa (1, 1) dintr-o matrice cu N linii şi M coloane. Fiecare căsuţă din matrice conţine o literă mică a alfabetului englez. În vis, el avea o misiune destul de grea. Pornind din căsuţa (1, 1), acesta trebuia să ajungă în căsuţa (N, M) din matrice, mergând la fiecare pas doar în dreapta sau în jos. Pentru că există foarte multe astfel de drumuri iar Moş Ene îşi dă seama că Trăncănici va vorbi foarte mult gândindu-se la toate posibilităţile, visul îi cere să aleagă drumul minim lexicografic.

Date de intrare

Fişierul de intrare drum6.in conţine pe prima linie două numere naturale N şi M, reprezentând dimensiunile matricei. Fiecare din următoarele N linii conţin câte M caractere (litere mici ale alfabetului englez), reprezentând conţinutul matricei.

Date de ieşire

În fişierul de ieşire drum6.out se va găsi un şir format din N + M - 1 caractere, reprezentând drumul minim lexicografic din căsuţa (1, 1) în căsuţa (N, M) a matricei.

Restricţii

  • 1 ≤ N, M ≤ 1000

Exemplu

drum6.indrum6.out
5 5
abfsd
asfkg
mcxjf
sdgjg
sdgkj
aamcddgkj
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?