Un păianjen a ţesut o plasă, în care nodurile sunt dispuse sub forma unui caroiaj cu m linii (numerotate de la 0 la m-1) şi n coloane (numerotate de la 0 la n-1) ca în figură.
Iniţial, oricare două noduri vecine (pe orizontală sau verticală) erau unite prin segmente de plasă de lungime 1. În timp unele porţiuni ale plasei s-au deteriorat, devenind nesigure. Pe plasă, la un moment dat, se găsesc păianjenul şi o muscă, în noduri de coordonate cunoscute.
Cerinţă
Să se determine lungimea celui mai scurt traseu pe care trebuie să-l parcurgă păianjenul, folosind doar porţiunile sigure ale plasei, pentru a ajunge la muscă. De asemenea, se cere un astfel de traseu.
Date de intrare
Fişierul de intrare paianjen.in conţine:
– pe prima linie două numere naturale m n, separate printr-un spaţiu, reprezentând numărul de linii şi respectiv numărul de coloane ale plasei;
– pe a doua linie două numere naturale lp cp, separate printr-un spaţiu, reprezentând linia şi respectiv coloana nodului în care se află iniţial păianjenul;
– pe linia a treia două numere naturale lm cm separate printr-un spaţiu, reprezentând linia şi respectiv coloana pe care se află iniţial musca;
– pe linia a patra, un număr natural k, reprezentând numărul de porţiuni de plasă deteriorate;
– pe fiecare dintre următoarele k linii, câte patru valori naturale l1 c1 l2 c2, separate prin câte un spaţiu, reprezentând coordonatele capetelor celor k porţiuni de plasă deteriorate (linia şi apoi coloana pentru fiecare capăt).
Date de ieşire
Fişierul de ieşire paianjen.out va conţine pe prima linie un număr natural min reprezentând lungimea drumului minim parcurs de păianjen, exprimat în număr de segmente de lungime 1. Pe următoarele min+1 linii sunt scrise nodurile prin care trece păianjenul, câte un nod pe o linie. Pentru fiecare nod sunt scrise linia şi coloana pe care se află, separate printr-un spaţiu.
Restricţii
1 <= m, n <= 140
1 <= k <= 2*(m*n-m-n+1)
Lungimea drumului minim este cel mult 15000.
Pentru datele de test există întotdeauna soluţie. Dacă problema are mai multe soluţii, se va afişa una singură.
Porţiunile nesigure sunt specificate în fişierul de intrare într-o ordine oarecare. Oricare două porţiuni nesigure orizontale se pot intersecta cel mult într-un capăt. De asemenea, oricare două porţiuni nesigure verticale se pot intersecta cel mult într-un capăt.
Se acordă 30% din punctaj pentru determinarea lungimii drumului minim şi 100% pentru rezolvarea ambelor cerinţe.
