!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ă şi fără să treacă de două ori prin aceeaşi poziţie până la un alt punct $(e,M)$ situat pe latura de est.

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ţă

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.

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!

!problema/gheizere?explicatie.jpg 200x200!

== include(page="template/taskfooter" task_id="gheizere") ==

7738