In lumea World of Warcraft este foarte importanta comunicarea intre cele M cele mai
puternice aliante. Periodic cate un reprezentant din fiecare alianta trebuie sa mearga la o intalnire super ultra mega secreta
unde se decide ce vor face in viitor.
Fiindu-le incomod sa calatoreasca distante lungi pe jos, ei ar vrea sa se intalneasca intr-un loc in care suma distantelor parcurse
de reprezentanti sa fie minima.
Jucatorii de WoW stiu urmatoarele lucruri despre lumea jocului:
Lumea este reprezentata ca o matrice cu N linii si P coloane.
Pozitia fiecarui membru reprezentant al aliantelor este cunoscuta.
In lumea lor sunt locuri periculoase marcate cu 1 in matricea
care reprezinta lumea jocului, iar cele sigure sunt marcate cu 0.
Reprezentantii se pot deplasa in una dintre directiile sus,
jos, stanga si dreapta dar nu pot merge intr-un loc periculos. O astfel de
deplasare are distanta 1.
Avand la dispozitie toate aceste informatii, ei tot nu pot calcula un loc de intalnire care sa indeplineasca conditiile. Tu
poti?
Cerinţă
Scrieti un program care sa determine un loc pentru intalnire L=(X, Y) cu proprietatea ca suma distantelor parcurse de reprezentanti pentru a
ajunge la el este minima. De asemenea programul trebuie sa calculeze si suma distantelor parcurse de reprezentanti pana la punctul
L.
Date de intrare
Fisierul de intrare wow.in
contine pe prima linie 3 numere naturale N P M reprezentand numarul de linii, numarul de
coloane ale matricei si respectiv numarul de reprezentanti ai
aliantelor. Pe urmatoarele N linii sunt cate P valori de 1 si
0 reprezentand elementele matricei (1 indicand zonele periculoase, iar 0 pe cele sigure).
Pe urmatoarele M linii sunt perechi de numere (X, Y) reprezentand locurile curente ale reprezentantilor. Valorile scrise pe aceeasi linie sunt separate prin spatiu. Perechea
(0, 0)
reprezinta coltul din stanga sus al matricei, iar perechea (N-1, P-1) coltul
din dreapta jos.
Date de ieşire
Fisierul de iesire wow.out va contine pe prima linie un numar care reprezinta suma
distantelor parcurse de reprezentanti pana la punctul L. A doua linie va contine
doua numere X si Y separate prin spatiu, reprezentand
linia, respectiv coloana punctului L.
Daca sunt mai multe puncte care satisfac
proprietatea lui L se va afisa cel mai mic lexicografic (cel care are X minim, iar daca sunt mai multe cu acelasi X minim, acela dintre acestea care are Y minim).
Restricţii
2 <=
N, P <= 100
2 <=
M <= 1500
0<=
X < N
0 <=
Y < P
Pentru datele de test, exista cel putin un loc in care se pot intalni toti
reprezentantii.
Pozitiile reprezentantilor sunt marcate cu R. Locul de intalnire care este marcat cu L
R 0 1 0 0 0 1 0 0 0 0 1 R 0 0 L 0 0 0 0 R 0 0 0 0
4 4 2 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 3 2
5 0 0
Locurile posibile de intalnire sunt marcate cu L. Ele se suprapun cu locurile de start ale celor 2 reprezentanti. Solutia cea mai mica lexicografica este 0 0.