Bugs Bunny se ascunde intr-o livada de la marginea padurii.
Livada contine m x n copaci,
asezati sub forma unei matrice cu m
linii si n coloane, distanta
dintre oricare doi pomi alaturati (pe verticala sau orizontala) fiind egala
cu 1. Liniile sunt numerotate
de la 1 la m,
de la Nord la Sud, iar coloanele sunt numerotate de la 1
la n, de la Vest la Est. Astfel,
pozitia unui copac din livada poate fi identificata prin numarul liniei si respectiv
numarul coloanei pe care se afla copacul.
Padurea incepe de la marginea de Est a livezii (dupa coloana n)
si este atat de deasa incat orice animal este in siguranta acolo. Iepurasul
isi are vizuina la radacina unui copac.
Iata ca in livada a aparut un vanator. El si-a fixat pozitia langa un copac si incearca sa vaneze iepurele, fara a-si schimba pozitia.
Simtindu-se in pericol, iepurasul intentioneaza sa ajunga in padure. Pentru
aceasta el se poate deplasa in 4 directii (Nord, Sud, Est, Vest), facand salturi
de lungime 1. Dupa fiecare salt,
iepurasul se opreste cateva secunde, timp în care este vulnerabil, daca vanatorul
il vede.
Spunem ca vanatorul vede iepurasul daca pe segmentul ce uneste copacul langa care sta vanatorul si copacul langa care se afla iepurasul nu exista nici un alt copac.
Cerinta
Cunoscand dimensiunile livezii, pozitia vanatorului si pozitia
vizuinii iepurasului, determinati riscul minim la care se expune iepurasul de
la vizuina pana la padure. Riscul unui drum este egal cu numarul de pomi de
pe drum in care iepurasul este vazut de vanator. Cum exista mai multe drumuri
de risc minim, ne intereseaza si care este lungimea minima a unui astfel de
drum (exprimata in numar de salturi efectuate de iepuras pana a ajunge in padure).
Date de intrare
Fisierul de intrare iepuras2.in are pe prima linie numarul de
linii m si numarul de coloane n ale livezii.
Pe linia a doua se gasesc doua numere naturale Lv si Cv,
separate prin spatiu, care reprezinta linia si coloana pe care pandeste vanatorul, iar pe linia a treia doua numere naturale
Li si Ci, separate printr-un spatiu,
reprezentand linia si coloana vizuinii iepurasului.
Date de iesire
Fisierul de iesire iepuras2.out
va contine doua linii. Pe prima linie pe care va fi scris un singur numar natural
R - riscul minim la care se expune
iepurasul de la vizuina spre padure. Pe cea de a doua linie va fi scris numarul
minim de salturi pe care trebuie sa le execute iepurasul pe un drum de risc
minim care ajunge la padure.
Restrictii si precizari
1 <= m, n, Lv, Cv, Li, Ci <= 250
Pozitia vanatorului este una de risc infinit pentru iepuras.
Iepurasul nu poate fi vazut cand se afla in vizuina.
Odata ajuns pe coloana n, iepurasul mai trebuie sa faca un salt pentru a fi in siguranta in padure.
Exemple
iepuras2.in
iepuras2.out
Explicatie
5 4
3 2
3 1
3
6
3 - este riscul minim al drumurilor.
6 - este numarul minim de salturi pe un drum de risc minim.
Exista mai multe drumuri de risc minim 3. Tuturor, le corespunde acelasi numar minim de salturi, 6.
3 3
2 1
3 1
2
3
2 - este riscul minim al drumurilor.
3 - este numarul minim de salturi pe un drum de risc minim.
Exista doua drumuri de risc minim 2.
Unuia ii corespund 3 salturi,
iar celuilalt 4 salturi.
4 4
1 3
1 1
3
6
3 - este riscul minim al drumurilor.
6 - este numarul minim de salturi pe un drum de risc minim.
Exista mai multe drumuri de risc minim 3.Unora dintre acestea, le corespunde cel mai mic numar de salturi, 6.