Soricelul duce un razboi continuu cu dusmanul traditional. Terenul de lupta
este curtea, reprezentata pe harta soricelului de un dreptunghi de dimensiuni
intregi, impartit, pentru o mai usoara orientare, in patrate de dimensiune 1. Pe
harta sunt marcate pozitiile (patratele) unde se gasesc adaposturile soricelului
si pozitiile unde se gasesc rezervele sale de hrana. Soricelul, care se gaseste
intr-un adapost, vrea sa se furiseze pana la un depozit de hrana de unde sa-si
ia portia de mancare si sa fuga repede intr-un alt adapost.Cat mai repede inseamna
cu cat mai putini pasi, un pas reprezentand deplasarea de la un patrat de pe
harta la unul invecinat pe orizontala, verticala sau diagonal.
Cerinta
Cunoscand configuratia hartii si pozitia initiala a soricelului determinati
depozitul de hrana si adapostul in care revine acesta astfel ca numarul total
de pasi facuti sa fie minim
Date de intrare
Pe prima linie a fisierului de intrare soricel1.in
sunt scrise doua numere reprezentand dimensiunile hartii. Pe a doua linie este
scris numarul de adaposturi, iar pe urmatoarele linii pozitia acestora. In continuare,
pe o linie noua se gaseste numarul de depozite de hrana urmat de linii pe care
se gasesc coordonatele acestor depozite. In fine, pe ultima linie se gaseste
numarul de ordine al adapostului in care se afla soricelul. Numerele de pe aceeasi
linie sunt separate de un spatiu. Coordonatele care precizeaza pozitia unui
adapost sau depozit de hrana sunt doua numere naturale - linia si coloana patratului
respectiv. Numerotarea liniilor si a coloanelor incepe de la 1. Numerele de
ordine ale adaposturilor, respectiv depozitelor, incep de la 1 si respecta ordinea
in care au fost scrise in fisierul de intrare.
Date de iesire
In fisierul soricel1.out
se va scrie pe prima linie numarul de ordine al depozitului de hrana ales iar
pe a doua linie numarul de ordine al adapostului in care se va retrage soricelul.
Daca sunt mai multe solutii posibile se va scrie cea care are numarul de ordine
al depozitului de hrana cat mai mic, iar daca sunt doua solutii cu acelasi
depozit se va scrie cea in care numarului adapostului este cat mai mic.
Restrictii
Dimensiunile hartii sunt cel mult 200 x 200, exista cel mult 500 de adaposturi
si cel mult 500 de depozite de hrana. Nici un depozit de hrana nu coincide cu
un adapost.
Exemplu
soricel1.in
soricel1.out
5 6
3
1 3
4 4
2 6
2
3 6
5 2
1
1
3
prof. Nistor Mot
Colegiul National "N. Balcescu"- Braila