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 forma 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 aceasta zona 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ânda pentru a ataca cârtita în momentele ei de neatenție.
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 forma 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 aceasta zona 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ânda pentru a ataca cârtita în momentele ei de neatenție.
Pe suprafața terenului cârtita se poate deplasa din pătrățelul în care se afla 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 orizontala și verticala, 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ționață î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 agricola. 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 viata î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 exista doua galerii care sa 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 sa se plimbe prin toate galeriile de sub teren trecând o singura data prin fiecare, dar pentru acest lucru trebuie sa ajungă nevătămată mergând la suprafața terenului la un pătrățel de unde să intre în sistemul de galerii.
Cerința
Determinați:
1. cel mai apropiat pătrățel de poziția inițială a cârtitei prin care ea poate să intre în galerie pentru a se plimba, precum și lungimea traseului parcurs la suprafață astfel încât fiecare pătrățel de pe traseu sa 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 afla numerele naturale M și N, reprezentând dimensiunile zonei agricole. Pe a treia linie se afla xc yc, coordonatele cârtitei. Pe linia a patra se afla 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ârtita î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 sa fie același cu cel în care ajunge cârtita la sfârșitul plimbării și nu este obligatoriu sa fie același cu cel în care ea intra în galerii de la suprafața terenului.
Restricții
1 ≤ M,N ≤ 2001 ≤ G ≤ 1000 ≤ 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 reprezinta
50%din punctaj. - Cârtita nu poate intra în galerii printr-un pătrățel din raza de acțiune a unei vulpi.
- Pentru toate testele exista soluție la cerința a), adică exista un traseu sigur de la cârtiță la o intrare într-o galerie.
- Soluția, nu este unica, însa, orice soluție corecta va obține punctajul maxim pe test.
- Inițial, cârtita se găsește pe o poziție în care nu este atacata de nicio vulpe.
Exemplu 1
cartite.in
16 46 335 1 03 4 14 3 071 1 3 21 3 1 41 1 3 31 4 4 24 2 3 34 2 1 34 2 3 2
cartite.out
4 2 3
Exemplu 2
cartite.in
26 46 335 1 03 4 14 3 071 1 3 21 3 1 41 1 3 31 4 4 24 2 3 34 2 1 34 2 3 2
cartite.out
1 13 24 21 31 44 23 31 1
Explicație
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 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).
#include <bits/stdc++.h>
using namespace std;
const int N = 205, oo = 1e9;
using VI = vector<int>;
using VVI = vector<VI>;
VI dx = {1, -1, 0, 0, -2, 2, 1, 1, -1, -1, 0, 0};
VI dy = {0, 0, 1, -1, 0, 0, 1, -1, 1, -1, 2, -2};
VVI a(N, VI(N)), d(N, VI(N));
queue <pair<int, int>> q;
VI eulcycle;
vector<pair<int, int>> L[N * N];
bitset<105> used;
int n, m, task, xc, yc;
inline bool Inside (int x, int y)
{
return (x > 0 && y > 0 && x <= n && y <= m);
}
void Initiate ()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
d[i][j] = oo;
}
void Lee (int xc, int yc)
{
d[xc][yc] = 0;
q.push({xc, yc});
while (!q.empty())
{
int i = q.front().first;
int j = q.front().second;
q.pop();
for (int dir = 0; dir < 4; dir++)
{
int x = i + dx[dir];
int y = j + dy[dir];
if (Inside(x, y) && !a[x][y] && d[x][y] > 1 + d[i][j])
{
d[x][y] = 1 + d[i][j];
q.push({x, y});
}
}
}
}
inline int Convert(int x, int y)
{
return (x - 1) * m + y;
}
void Eulerian_Cycle(int start)
{
stack <int> st;
st.push(start);
while (!st.empty())
{
int currnode = st.top();
if (L[currnode].size())
{
pair <int, int> next = L[currnode].back();
L[currnode].pop_back();
if (!used[next.second])
{
used[next.second] = 1;
st.push(next.first);
}
}
else
{
st.pop();
eulcycle.push_back(currnode);
}
}
}
void Solve()
{
ifstream fin ("cartite.in");
int i, j, k, t, x, y, G;
fin >> task;
fin >> n >> m;
fin >> xc >> yc;
fin >> k;
for (i = 1; i <= k; i++)
{
fin >> x >> y >> t;
a[x][y] = 1;
if (t >= 1)
{
for (int dir = 0; dir < 4; dir++)
{
int xx = x + dx[dir];
int yy = y + dy[dir];
if (Inside(xx, yy))
a[xx][yy] = 1;
}
if (t == 2)
{
for (int dir = 4; dir < 12; dir++)
{
int xx = x + dx[dir];
int yy = y + dy[dir];
if (Inside(xx, yy))
a[xx][yy] = 1;
}
}
}
}
Initiate();
Lee(xc, yc);
fin >> G;
int mindist = oo, posx, posy, x1, y1;
for (int step = 1; step <= G; step++)
{
fin >> i >> j >> x1 >> y1;
if (d[i][j] < mindist)
{
mindist = d[i][j];
posx = i;
posy = j;
}
if (d[x1][y1] < mindist)
{
mindist = d[x1][y1];
posx = x1;
posy = y1;
}
y = Convert(x1, y1);
x = Convert(i, j);
L[x].push_back({y, step});
L[y].push_back({x, step});
}
ofstream fout ("cartite.out");
if (task == 1)
{
fout << posx << " " << posy << " " << mindist << "\n";
}
else
{
Eulerian_Cycle(Convert(posx, posy));
for (size_t i = 0; i < eulcycle.size(); i++)
{
int r = eulcycle[i] / m;
int mod = eulcycle[i] % m;
if (mod != 0) r++;
fout << r << " ";
if (mod == 0) mod = m;
fout << mod << "\n";
}
}
fout.close();
}
int main()
{
Solve();
return 0;
}
