Problem 33: cartite

Cârtițele sunt animale de dimensiuni mici care își duc traiul pe suprafețe de teren deschis, având ca dușman principal vulpea. Lângă o pădure se află o zonă agricolă în formă dreptunghiulară, împărțită în pătrățele de aceeași dimensiune. Zona agricolă este reprezentată printr-un tablou bidimensional cu m linii și n coloane, având liniile și coloanele numerotate începând cu 1. În această zonă agricolă trăiește o cârtiță și k vulpi.

Pentru cârtiță cunoaștem coordonatele ei (linia și coloana) pe care se găsește, la fel și pentru vulpi, care stau la pândă pentru a ataca cârtița în momentele ei de neatenție.

Pe suprafața terenului cârtița se poate deplasa din pătrățelul în care se află doar într-unul dintre cele 4 pătrățele vecine pe direcțiile nord, sud, est sau vest.

Vulpile pot ataca instantaneu pe o raza de acțiune de lungime 0, 1 sau 2 pe orizontală și verticală, inclusiv în poziția unde se găsesc, după care tot instantaneu se întorc în pozițiile inițiale. În figura de mai jos sunt desenate pătrățele unde poate ataca o vulpe poziționată în pătrățelul cu cifra reprezentând raza de acțiune.

Pentru a micșora riscul de deplasare în zona agricolă cârtița sapă în pământ un sistem de g galerii, care leagă între ele pătrățele din zona agricolă. Aceste galerii nu se intersectează sub pământ, ci doar la suprafață, trecerea dintr-o galerie în alta, care se intersectează în același pătrățel făcându-se printr-un sistem ce nu îi pune viața în pericol. Galeriile sunt indicate prin coordonatele pătrățelelor pe care le unesc. Acestea sunt săpate astfel încât, dacă pornim dintr-un capăt al unei galerii le putem parcurge pe toate. Nu există două galerii care să pornească din același pătrățel și să ajungă tot în același pătrățel (galeriile sunt distincte).

Cârtița dorește să se plimbe prin toate galeriile de sub teren trecând o singură dată prin fiecare, dar pentru acest lucru trebuie să ajungă nevătămată mergând la suprafață terenului la un pătrățel de unde să intre în sistemul de galerii.

Cerinţă

Determinați:
a) cel mai apropiat pătrățel de poziția inițială a cârtiței prin care ea poate să intre în galerie pentru a se plimba, precum și lungimea traseului parcurs la suprafață asfel încât fiecare pătrățică de pe traseu să nu fie atacată de nicio vulpe;
b) traseul de plimbare numai prin galerii, specificat prin coordonatele pătrăţelelor care constituie capetelor acestora.

Date de intrare

Fişierul de intrare cartite.in conţine următoarele date:

pe prima linie un număr natural p, pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2;
pe a doua linie m, n dimensiunile zonei agricole;
pe a treia linie coordonatele cârtiței;
pe linia a patra numărul de vulpi k urmată de k linii cu câte trei numere naturale reprezentând coordonatele pătrățelelor unde se găsesc vulpi și raza lor de acțiune (0, 1 sau 2);
următoarea linie conține numărul de galerii g;
fiecare din următoarele g linii conține câte 4 numere naturale separate prin câte un spațiu, reprezentând coordonatele capetelor unei galerii.

Date de ieşire

Dacă valoarea lui p este 1, se va afişa numai rezultatul de la punctul a) din cerință. În acest caz, în fişierul de ieşire cartite.out se vor scrie trei numere naturale separate între ele prin câte un spațiu, reprezentând coordonatele pătrățelului unde va intra cârtița în galerii și lungimea traseului parcurs la suprafață.

Dacă valoarea lui p este 2, se va afişa numai rezultatul de la punctul b) din cerință. În acest caz, fişierul de ieşire cartite.out va conține coordonatele pătrățelelor traseului de plimbare prin galerii (coordonatele câte unui pătrățel pe câte o linie, începând cu prima linie a fișierului de ieşire). Pătrățelul de pornire trebuie să fie același cu cel în care ajunge cârtița la sfârșitul plimbării și nu este obligatoriu să fie același cu cel în care ea intră în galerii de la suprafața terenului.

Restricţii şi precizări

1 ≤ m, n ≤ 200
1 ≤ g ≤ 100
0 ≤ k ≤ 50
Lungimea traseului parcurs la suprafață este egală cu numărul de pătrățele prin care aceasta trece, dar diferite de cel din care pleacă.
Fiecare dintre cerințe reprezintă 50% din punctaj.
Cârtița nu poate intra în galerii printr-un pătrățel din raza de acțiune a unei vulpi.
Pentru toate testele există soluție la cerința a), adică există un traseu sigur de la cârtiță la o intrare într-o galerie.
Soluția, nu este unică, însă, orice soluție corectă va obține punctajul maxim pe test.
Inițial, cârtița se găsește pe o poziție în care nu este atacată de nicio vulpe.

Exemple

cartite.in

cartite.out

4 2 3

cartite.in

cartite.out

Explicații

Pentru primul test:
p = 1
Deplasarea cârtiței pe suprafața agricolă se va face pe traseul de lungime 3 ce trece prin pătrățelele (6,3) (6,2) (5,2) (4,2). Coordonatele pătrățelului de intrare în galerii sunt (4,2).
Atenție! Pentru acest test se va afişa doar rezultatul la cerința a).

Pentru al doilea test:
p = 2
Traseul de plimbare prin galerii este următorul: (1,1) (3,2) (4,2) (1,3) (1,4) (4,2) (3,3) (1,1), cu observația că se putea alege și alt pătrățel de plecare.
Atenție! Pentru acest test se va afişa doar rezultatul la cerința b).
Se observă că în acest caz trebuie să se citească toate datele din fișier.

cartite