== include(page="template/taskheader" task_id="gheizere") ==
Într-o zonă vulcanică de formă dreptunghiulară de dimensiuni întregi $NxM$, împărţită în celule pătrate de latura $1$, există $P$ gheizere.
Gheizerele sunt izvoare intermitente de origine vulcanică, care emit în atmosferă la intervale regulate de timp jeturi de apă fierbinte şi/sau vapori, datorită încălzirii rapide a apelor din golurile subterane. Erupţia unui gheizer produce stropirea cu apă fierbinte a unei zone circulare cu centrul situat în punctul $(x,y)$ aflat pe linia $x$ şi coloana $y$, şi raza $r$, zona afectată fiind considerată zona delimitată de pătratul în care se înscrie cercul.
!problema/gheizere?enunt.jpg 200 x 200!
În figura alăturată avem 2 gheizere ce au coordonatele $(3,3)$ şi $(5,8)$, primul gheizer cu raza egală cu $1$, iar cel de-al doilea gheizer cu raza egală cu $2$. Pentru fiecare gheizer se cunoaşte intervalul de unităţi de timp $t$ consumat între erupţii, precum şi durata $d$ a unei erupţii, valori exprimate în secunde.
Misiunea unui cercetător este de a găsi un traseu ce pleacă dintr-un punct dat al terenului situat pe latura de vest $(v,1)$ şi traversează zona fără să o părăsească până la un alt punct $(e,M)$ situat pe latura de est.
Cercetătorul se poate deplasa în oricare dintre direcţiile $nord$, $est$, $sud$, iar timpul consumat pentru parcurgerea unei celule neafectate la un moment dat este de o secundă. Parcurgerea unei zone în care acţionează cel puţin un gheizer pe perioada de erupţie a acestuia implică riscuri majore pentru cercetător.
h2. Cerinţă
Să se determine timpul minim necesar traversării de la vest la est a zonei vulcanice de către cercetător fără riscuri majore.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $gheizere.in$ conţine:
* pe prima linie trei valori naturale $N$, $M$ şi $P$, unde $N$ reprezintă numărul de linii şi $M$ numărul de coloane ale zonei vulcanice, iar $P$ numărul de gheizere;
* pe a două linie două valori naturale $v$ respectiv $e$, unde $v$ reprezintă linia punctului de plecare din vest, iar $e$ linia punctului de sosire din est;
* pe următoarele $P$ linii un set de cinci valorii $x$, $y$, $r$, $t$, $d$ ce reprezintă în ordine, pentru fiecare gheizer coordonatele centrului $(x,y)$, $r$ raza cercului de erupţie, $t$ timpul dintre erupţii, iar $d$ durata unei erupţii.
Fişierul de intrare $gheizere.in$ ...
h2. Date de ieşire
Fişierul de ieşire $gheizere.out$ va conţine o singură valoare naturală $T$ ce reprezintă timpul minim necesar cercetătorului pentru a traversa zona vulcanică de la vest la est fără riscuri majore.
În fişierul de ieşire $gheizere.out$ ...
h2. Restricţii
* $2 ≤ N, M ≤ 250$
* $1 ≤ e, v ≤ N$
* $1 ≤ x ≤ N$, $1 ≤ y ≤ M$
* $1 ≤ P ≤ 1000$
* $1 ≤ r ≤ 5$
* $1 ≤ d ≤ 5$
* $2 ≤ t < 10$
* Două gheizere nu pot avea aceleaşi coordonate pentru centrul cercului.
* Iniţial toate gheizerele sunt inactive.
* Cercetătorul parcurge traseul fără să se oprească.
* Pentru datele de intrare există întotdeauna soluţie.
* Durata maximă a unui traseu parcurs de către cercetător este $≤ 1000$ secunde.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. gheizere.in |_. gheizere.out |
| 9 10 5
1 9
2 6 1 2 2
3 3 1 3 3
6 8 2 6 1
8 2 1 4 2
9 5 1 4 1
| 18
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Unul dintre traseele posibile care porneşte din (1,1) şi ajunge în (9,10) în timp minim este marcat, secundă cu secundă, în figura următoare.
Zonele influenţate de gheizere sunt marcate cu pătrate gri, iar centrul fiecărui gheizer este evidenţiat (bold).
!problema/gheizere?explicatie.jpg 200x200!
...
== include(page="template/taskfooter" task_id="gheizere") ==
== include(page="template/taskfooter" task_id="gheizere") ==
