== include(page="template/taskheader" task_id="delfin") ==
Poveste şi cerinţă...
_Delfinul e de fapt o ţestoasă. Naming maintained for legacy reasons._
Teognis, de curând la liceu, a început să capete puteri paranormale. Mai exact, el poate controla telepatic ţestoasa mascotă a liceului, Percy. Pătruns cumva în lumea mistică a ţestoaselor, el doreşte acum să captureze comoara magică a ţestoaselor.
Lumea ţestoaselor poate fi modelată ca o matrice cu N linii si M coloane, unde fiecare celulă conţine fie pământ fie apă. Teognis şi Percy se deplasează după următoarele reguli:
- Atât lui Teognis cât si lui Percy le ia o unitate de timp să se deplaseze dintr-o celulă într-o altă celulă adiacentă ortogonal (i.e, o celulă vecină pe una din cele patru direcţii cardinale).
- Ei au voie să se deplaseze simultan.
- Percy se va afla permanent pe celule cu apă.
- Teognis poate călători de unul singur doar pe celule cu pământ.
- Teognis poate călători pe apă dacă se află pe spatele lui Percy.
- Pentru a urca pe spatele lui Percy, Teognis trebuie să se deplaseze către o celulă cu apă în care Percy se afla deja sau în care s-a deplasat în exact acelaşi timp. Analizaţi primul exemplu pentru clarificări în această privinţă.
- Pentru a coborî de pe spatele lui Percy, Teognis trebuie să păşească pe o celulă cu pământ care este adiacentă poziţii curente. El poate urca şi coborî de pe Percy de oricâte ori.
Comoara magică a ţestoaselor se află undeva pe pământ. Care este timpul minim necesar pentru ca Teognis să ajungă la celula în care se află comoara?
h2. Date de intrare
Fişierul de intrare $delfin.in$ ...
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:
table(Inteles caractre). |_. Caracter |_. Semnificatie |
| $1$ | Pământ |
| $0$ | Apă |
| $S$ | Teognis (apare o singură dată) |
| $F$ | Comoara (apare o singură dată) |
| $D$ | Percy (apare o singură dată) |
h2. Date de ieşire
În fişierul de ieşire $delfin.out$ ...
În fişierul de ieşire $delfin.out$ se va afla un singur numar, timpul minim de a ajunge la comoara.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 1000$
* Pentru *15* de puncte se garantează ca N = 1
* Pentru alte *35* de puncte se garantează ca $1 ≤ N, M ≤ 50$
* Celulele în care se află iniţial Teognis, respectiv comoara, conţin pământ.
* Celula în care se află iniţial Percy conţine apă.
* Se garanteaza ca intotdeauna se poate ajunge la Comoara.
* Veţi primi rezultatele evaluării _doar_ pe fişierele de intrare din exemplu. Acestea nu vor afecta scorul problemei, având punctajul asociat 0.
h2. Exemplu
table(example). |_. delfin.in |_. delfin.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1 4
S0DF
| 3
|
| 5 7
S110000
1010000
0010000
0000000
D00000F
| 10
|
| 13 8
S1111111
00000001
11111101
10000001
10111111
10100000
10111111
10000001
11111101
00000101
11111101
1D000000
1111111F
| 29
|
h3. Explicaţie
...
În primul exemplu Percy se va apropia de Teognis cu o celulă, iar în acelaşi moment Teognis i se va urca pe spate. Apoi Percy se va deplasa cu o celulă către comoară, iar Teognis va folosi încă o unitate de timp pentru a coborî de pe Percy exact în celula cu comoara.
În cel de al doilea exemplu Teognis se va urca pe Percy la celula $(4, 3)$ şi îi va lua 5 unităţi de timp să facă acest lucru (Percy, fiind la distanţă $3$ de această celulă, poate fi prezent la punctul de întâlnire încă de la momentul $3$). Apoi vor călători împreună încă $5$ unităţi de timp până când Teognis va coborî direct pe celula care conţine comoara.
== include(page="template/taskfooter" task_id="delfin") ==
