== include(page="template/taskheader" task_id="cartite") ==
Poveste şi cerinţă...
Cârtitele sunt animale de dimensiuni mici care îsi duc traiul pe suprafete de teren deschis, având ca dusman principal vulpea. Lânga o padure se afla o zona agricola în forma dreptunghiulara, împartita în patratele de aceeasi dimensiune. Zona agricola este reprezentata printr-un tablou bidimensional cu $M$ linii si $N$ coloane, având liniile si coloanele numerotate începând cu $1$. În aceasta zona agricola traieste o cârtita si $K$ vulpi.
Pentru cârtita cunoastem coordonatele ei (linia si coloana) pe care se gaseste, la fel si pentru vulpi, care stau la pânda pentru a ataca cârtita în momentele ei de neatentie.
Pe suprafata terenului cârtita se poate deplasa din patratelul în care se afla doar într-unul dintre cele 4 patratele vecine pe directiile nord, sud, est sau vest.
Vulpile pot ataca instantaneu pe o raza de actiune de lungime $0$, $1$ sau $2$ pe orizontala si verticala, inclusiv în pozitia unde se gasesc, dupa care tot instantaneu se întorc în pozitiile initiale. În figura de mai jos sunt desenate patratele unde poate ataca o vulpe pozitionata în patratelul cu cifra reprezentând raza de actiune.
!problema/cartite?9fwilz.jpg!
Pentru a micsora riscul de deplasare în zona agricola cârtita sapa în pamânt un sistem de $G$ galerii, care leaga între ele patratele din zona agricola. Aceste galerii nu se intersecteaza sub pamânt, ci doar la suprafata, trecerea dintr-o galerie în alta, care se intersecteaza în acelasi patratel facându-se printr-un sistem ce nu îi pune viata în pericol. Galeriile sunt indicate prin coordonatele patratelelor pe care le unesc. Acestea sunt sapate astfel încât, daca pornim dintr-un capat al unei galerii le putem parcurge pe toate. Nu exista doua galerii care sa porneasca din acelasi patratel si sa ajunga tot în acelasi patratel (galeriile sunt distincte).
Cârtita doreste sa se plimbe prin toate galeriile de sub teren trecând o singura data prin fiecare, dar pentru acest lucru trebuie sa ajunga nevatamata mergând la suprafata terenului la un patratel de unde sa intre în sistemul de galerii.
h2. Cerinta
Determinati:
1.cel mai apropiat patratel de pozitia initiala a cârtitei prin care ea poate sa intre în galerie pentru a se plimba, precum si lungimea traseului parcurs la suprafata asftel încât fiecare patratica de pe traseu sa nu fie atacata de nicio vulpe;
2.traseul de plimbare numai prin galerii, specificat prin coordonatele patratelelor care constituie capetelor acestora.
h2. Date de intrare
Fişierul de intrare $cartite.in$ ...
Fisierul de intrare cartite.in contine pe prima linie un numar natural $p$, care poate avea doar valoarea $1$ sau valoarea $2$. Pe a doua linie se afla numerele naturale $M$ si $N$, reprezentând dimensiunile zonei agricole. Pe a treia linie se afla $x{~c~} y{~c~}$, coordonatele cârtitei. Pe linia a patra se afla numarul de vulpi $K$, apoi urmeaza $K$ linii cu câte trei numere naturale reprezentând coordonatele patratelelor unde se gasesc vulpi si raza lor de actiune $(0, 1 sau 2)$. Urmatoarea linie contine numarul de galerii $G$. Fiecare dintre urmatoarele $G$ linii contine câte $4$ numere naturale separate prin câte un spatiu, reprezentând coordonatele capetelor unei galerii.
h2. Date de ieşire
h2. Date de iesire
În fişierul de ieşire $cartite.out$ ...
Daca valoarea lui $p$ este $1$, se va afisa numai rezultatul de la cerinta $1$. În acest caz, în fisierul de iesire cartite.out se vor scrie trei numere naturale separate între ele prin câte un spatiu, reprezentând coordonatele patratelului unde va intra cârtita în galerii si lungimea traseului parcurs la suprafata.
Daca valoarea lui $p$ este $2$, se va afisa numai rezultatul de la cerinta $2$. În acest caz, fisierul de iesire cartite.out va contine coordonatele patratelelor traseului de plimbare prin galerii (coordonatele câte unui patratel pe câte o linie, începând cu prima linie a fisierului de iesire). Patratelul de pornire trebuie sa fie acelasi cu cel în care ajunge cârtita la sfârsitul plimbarii si nu este obligatoriu sa fie acelasi cu cel în care ea intra în galerii de la suprafata terenului.
h2. Restricţii
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ M,N ≤ 200$
* $1 ≤ G ≤ 100$
* $0 ≤ K ≤ 50$
* Lungimea traseului parcurs la suprafata este egala cu numarul de patratele prin care aceasta trece, dar diferite de cel din care pleaca.
* Fiecare dintre cerinte reprezinta $50%$ din punctaj.
* Cârtita nu poate intra în galerii printr-un patratel din raza de actiune a unei vulpi.
* Pentru toate testele exista solutie la cerinta a), adica exista un traseu sigur de la cârtita la o intrare într-o galerie.
* Solutia, nu este unica, însa, orice solutie corecta va obtine punctajul maxim pe test.
* Initial, cârtita se gaseste pe o pozitie în care nu este atacata de nicio vulpe.
h2. Exemplu
table(example). |_. cartite.in |_. cartite.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
6 4
6 3
3
5 1 0
3 4 1
4 3 0
7
1 1 3 2
1 3 1 4
1 1 3 3
1 4 4 2
4 2 3 3
4 2 1 3
4 2 3 2
| 4 2 3
|
| 2
6 4
6 3
3
5 1 0
3 4 1
4 3 0
7
1 1 3 2
1 3 1 4
1 1 3 3
1 4 4 2
4 2 3 3
4 2 1 3
4 2 3 2
| 1 1
3 2
4 2
1 3
1 4
4 2
3 3
1 1
|
h3. Explicaţie
h3. Explicatie
Primul exemplu:
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).**
Al doilea exemplu:
Traseul de plimbare prin galerii este urmatorul: $(1,1) (3,2) (4,2) (1,3) (1,4) (4,2) (3,3) (1,1)$, cu observatia ca se putea alege si alt patratel de plecare.
**Atentie! Pentru acest test se va afisa doar rezultatul la cerinta b).**
...
== include(page="template/taskfooter" task_id="cartite") ==
== include(page="template/taskfooter" task_id="cartite") ==
