Soricel 3
Eternul si fascinantul teren de lupta dintre cei doi protagonisti celebri, pisica si soarecele, este din nou in atentia soricelului. Acesta studiaza harta curtii pentru a gasi o modalitate de deplasare prin curte cat mai lipsita de pericole. Harta este un dreptunghi de dimensiuni intregi m x n, impartit in celule patrate de latura 1; o celula este precizata printr-o pereche de numere intregi - numarul liniei si numarul coloanei in care se gaseste (liniile si coloanele sunt numerotate incepand de la 1).
Pe harta sunt insemnate celulele in care pisica obisnuieste sa stea la panda. Gradul de periculozitate al unei celule este in functie de distanta pana la cel mai apropiat punct de panda al pisicii, mai exact este lungimea curtii + latimea curtii - distanta pana la cel mai apropiat punct de panda.
Gradul de periculozitate al unui drum este dat de suma gradelor de periculozitate ale celulelor traversate. Atat soricelul cat si pisica se pot deplasa de la o celula la una invecinata pe orizontala sau verticala, iar distanta dintre doua celule este data de numarul minim de celule traversate intr-o deplasare de la o celula la cealalta minus 1. De exemplu distanta dintre celulele (1,1) si (2,2) este 2.
Cerinta
Scrieti un program care determina un drum de la celula (1,1) - coltul stanga-sus, la celula (m,n) - coltul dreapta-jos cu gradul de periculozitate minim.
Date de intrare
Pe prima linie a fisierului de intrare soricel3.in sunt scrise doua numere m si n - dimensiunile hartii.
Pe urmatoarea linie este scris numarul p al pozitiilor in care se poate afla pisica (pozitii de panda).
Pe urmatoarele p linii sunt scrise coordonatele - linia si coloana - celulelor in care poate sta la panda pisica.
Date de iesire
Prima linie a fisierului soricel3.out contine doua numere intregi - gradul de periculozitate minim al drumului gasit si numarul celulelor care alcatuiesc acest drum.
Pe urmatoarele linii se gasesc coordonatele celulelor ce alcatuiesc acest drum, in ordinea traversarii, incepand cu (1,1) si terminand cu (m,n). In ambele fisiere coordonatele scrise pe o linie sunt separate de un spatiu. Daca exista mai multe solutii se va alege una oarecare.
Restrictii
Exemplu
|
soricel3.in |
soricel3.out |
|
4 4 |
42 7 |
| 2 | 1 1 |
| 2 1 | 1 2 |
| 2 4 | 2 2 |
| 3 2 | |
| 4 2 | |
| 4 3 | |
| 4 4 |
Timp maxim de executie/test: 0.5 secunde
prof. Nistor Mot
Colegiul National "N.Balcescu" - Braila