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ţa terenului la un pătrăţel de unde să intre în sistemul de galerii.
Cerinţă
Determinaţi:
1. 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ţă asftel încât fiecare pătrăţică de pe traseu să nu fie atacată de nicio vulpe;
2. 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 pe prima linie un număr natural p, care poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se află numerele naturale m n, reprezentând dimensiunile zonei agricole. Pe a treia linie se află xc yc, coordonatele cârtiţei. Pe linia a patra se află numărul de vulpi k, apoi urmează 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 dintre 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 cerinţa 1. Î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 cerinţa 2. Î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
• 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.
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.
