Î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.
Î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.
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.
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.
Date de intrare
Fişierul 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.
Date de ieşire
Fişierul 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.
Restricţii
• 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.
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).
