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
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 ?
Date de intrare
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:
| caracter | inteles |
|---|---|
| 1 | pamant |
| apa | |
| S | Teognis (apare odata) |
| F | Comoara (apare odata) |
| D | Percy (apare odata) |
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
- 1 ≤ N, M ≤ 2000
Exemplu
| delfin.in | delfin.out |
|---|---|
| 13 8 S1111111 00000001 11111101 10000001 10111111 10100000 10111111 10000001 11111101 00000101 11111101 1D000000 1111111F | 29 |
Explicaţie
...
