== include(page="template/taskheader" task_id="delfin") ==

Poveste şi cerinţă...

Teognis, de curand la liceu, a inceput sa capete puteri paranormale. Mai exact, el poate controla telepatic testoasa mascota a liceului, Percy. Patruns cumva in lumea mistica a testoaselor, el doreste acum sa captureze comoara magica a testoaselor.
Lumea testoaselor poate fi modelata ca o matrice cu N linii si M coloane, unde fiecare celula contine fie pamant fie apa. Atat lui Teognis, cat si lui Percy le ia o unitate de timp sa se deplaseze dintr-o celula intr-una adiacenta ortogonal; ei au voie sa se deplaseze simultan, dar si sa stea pe loc in timp ce celalalt se misca. Percy se poate afla doar pe apa, iar Teognis doar pe pamant. Comoara magica a testoaselor se aflta pe pamant. Pentru a putea trece peste apa, Teognis trebuie sa se urce pe Percy, care il poate duce peste apa. Care este timpul minim necesar pentru a castiga comoara ?

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?

h2. Date de intrare

1 <= N, M <= 2000

Fişierul de intrare $delfin.in$ contine pe prima linie N si M, 2 numere intregi reprezentand dimensiunea matricii ce reprezinta lumea testoaselor
Urmatoarele N linii vor contine cate M caractere, reprezentand matricea ce reprezinta lumea testoaselor. Fiecare celula a matricii contine un caracter, iar intelesul acestora este:

h2. Date de intrare

table(Inteles caractre). |_. caracter |_. inteles |
| 1 | pamant |
| 0 | apa |
| S | Teognis (apare odata) |
| F | Comoara (apare odata) |
| D | Percy (apare odata) |

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.

h2. Date de ieşire

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 2000$

h2. Exemplu