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 |
Vezi solutiile trimise | Statistici
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.
Date de ieşire
În fişierul de ieşire delfin.out se va afla un singur numar, timpul minim de a ajunge la comoara.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| delfin.in | delfin.out |
|---|---|
| 13 8 S1111111 00000001 11111101 10000001 10111111 10100000 10111111 10000001 11111101 00000101 11111101 1D000000 1111111F | 29 |
Explicaţie
...
