Diferente pentru problema/delfin intre reviziile #4 si #38

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="delfin") ==
Poveste şi cerinţă...
_Delfinul e de fapt o ţestoasă. Naming maintained for legacy reasons._
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?
Teognis, de curând la liceu, a început să capete puteri paranormale. Mai exact, el poate controla telepatic ţestoasa mascotă a liceului, Percy. truns cumva în lumea misti a ţestoaselor, el doreşte acum captureze comoara magi a ţestoaselor.
1 <= N, M <= 2000
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$ contine pe prima linie N si M, 2 numere intregi reprezentand dimensiunea matricei. Pe cea de-a doua linie vor fi 6 numere intregi X, Y, A, B, Z, T, unde X, Y reprezinta coordonatele in care te afli initial, A si B coordonatele initiale ale testoasei si Z si T coordonatele comorii de pe plansa.
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ă) |
Urmatoarele N linii vor contine cate N coloane, reprezentand o matrice binara asociata plansei. O celula cu valoarea 1 este o celula de pamant si o celula cu valoarea 0 este o celula de apa.
h2. Date de ieşire
h2. Restricţii
* $... &le; ... &le; ...$
* $1 &le; N, M &le; 1000$
* Pentru *15* de puncte se garantează ca N = 1
* Pentru alte *35* de puncte se garantează ca $1 &le; N, M &le; 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 |
| 1 4
S0DF
| 3
|
| 5 7
S110000
1010000
0010000
0000000
D00000F
| 10
|
| 13 8
1 1 12 2 13 8
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1
1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1
1 0 1 0 0 0 0 0
1 0 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 0 1
0 0 0 0 0 1 0 1
1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
| This is another
  text written on
  multiple lines.
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") ==
 

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.