Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-03-07 10:28:26.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	delfin.in, delfin.out	Sursă	Algoritmiada 2018 Runda PreOJI
Autor	Mihai Calancea	Adăugată de	Radu Muntean •heracle
Timp execuţie pe test	0.6 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Delfin

Poveste şi cerinţă...

Ai o matrice de N x M. Fiecare celula este fie pamant, fie apa. Tu esti undeva pe pamant. Exista o comoara, tot pe pamant. Exista o testoasa undeva pe apa. Iti este prietena, ii poti controla miscarile telepatic. Te poti misca in paralel cu testoasa. Ea te poate lua in spate si te poate duce pe apa. Care este timpul minim ca sa ajungi la comoara?

1 <= N, M <= 2000

Date de intrare

Fişierul de intrare delfin.in contine pe prima linie N si M, 2 numere intregi reprezentand dimensiunea matricei.
Urmatoarele N linii vor contine cate N caractere, reprezentand o matrice asociata plansei. O celula cu valoarea 1 este o celula de pamant, o celula cu valoarea 0 este o celula de apa, unica cu caracterul 'S' este pozitia initiala, unica cu caracterul 'F' este pozitia finala si unica cu caracterul 'D' este pozitia initiala a testoasei.