Fişierul intrare/ieşire:cub.in, cub.outSursăONI 2006, clasa 10
AutorAlin BurtaAdăugată demarcelcodreaCodrea Marcel marcelcodrea
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cub

Statia de cercetari astronomice ONI-2006 are forma unui cub cu latura de lungime N unitati. Fiecare dintre cele 6 fete ale statiei este impartita in N x N patrate cu latura unitate. Cosmonautii insarcinati cu intretinerea statiei se pot deplasa pe suprafata cubului, folosind sine speciale plasate in unele dintre patratelele unitate, pentru a efectua diverse reparatii. Unele patrate unitate, dintre cele prevazute cu sine, contin trape de intrare in interiorul statiei.
Din cauza radiatiilor cosmice nocive, cosmonautii trebuie sa petreaca un timp cat mai scurt in exteriorul statiei astfel incat, dupa terminarea unei reparatii, acestia trebuie sa se reintoarca in interiorul statiei utilizand cea mai apropiata trapa de acces. Cosmonautul se afla initial intr-un patratel prevazut cu sine. El se poate deplasa dintr-un patratel ce contine sine, in altul, aflat in vecinatatea pozitiei curente (pe orizontala sau verticala), patratel prevazut de asemenea cu sine. Cosmonautul se poate deplasa si de pe o fata a cubului pe o fata vecina, traversand latura comuna.
Fetele cubului sunt descrise conform figurii de mai jos.


Fata 1: ABCD - elementul (1,1) in A si elementul (N,N) in C
Fata 2: DCC'D'- elementul (1,1) in D si elementul (N,N) in C'
Fata 3: B'A'D'C'- elementul (1,1) in B' si elementul (N,N) in D'
Fata 4: BAA'B'- elementul (1,1) in B si elementul (N,N) in A'
Fata 5: CBB'C'- elementul (1,1) in C si elementul (N,N) in B'
Fata 6: ADD'A'- elementul (1,1) in A si elementul (N,N) in D'

Scrieti un program care sa determine distanta minima de la pozitia initiala a cosmonautului pana la o trapa de acces, precum si numarul trapelor aflate la distanta minima.

Date de intrare

Datele de intrare se citesc din fisierul cub.in, care are urmatoarea structura:
Pe prima linie se afla doua numere naturale N si K, separate printr-un spatiu, reprezentand lungimea laturii cubului, respectiv numarul trapelor de acces.
Pe a doua linie avem numerele naturale F, L, C, separate prin spatiu, desemnand patratul unitate pe care se afla initial cosmonautul, unde F{1,2,3,4,5,6} reprezinta numarul unei fete a cubului, iar L si C reprezinta coordonatele pozitiei initiale a cosmonautului, relative la coltul (1,1) al fetei cu numarul F ( L - numarul liniei, C - numarul coloanei)
Pe urmatoarele K linii se afla cate 3 numere naturale, separate prin spatiu, reprezentand coordonatele celor K trape de acces (numarul fetei, numarul liniei, respectiv numarul coloanei).
Pe urmatoarele 6N linii se afla cele 6 matrice patratice care descriu fetele cubului, avand elemente din multimea {0, 1} ( 0 - sina de acces, 1- patrat inaccesibil). Elementele unei fete sunt date pe linii, de la (1,1) pana la (N,N).

Date de iesire

Rezultatele se scriu in fisierul cub.out, care are urmatoarea structura:
Pe prima linie se va scrie numarul natural LG, reprezentand lungimea drumului minim parcurs de cosmonaut. Lungimea drumului este data de numarul patratelor unitate parcurse, inclusiv pozitia initiala si pozitia finala. Pe a doua linie se va afisa numarul natural T, reprezentand numarul trapelor de acces aflate la distanta minima fata de pozitia initiala a cosmonautului.

Restrictii

  • 1 ≤ N ≤ 50
  • 1 ≤ F ≤ 6
  • 1 ≤ L,C ≤ N
  • Cosmonautul se afla initial intr-o pozitie accesibila (prevazuta cu sina).
  • Exista cel putin o trapa accesibila din pozitia initiala a cosmonautului.

Exemplu

cub.incub.out
3 2
2 2 3
5 2 2
3 2 2
1 1 1
1 0 0
1 0 1
0 0 1
0 1 0
0 0 0
1 1 1
1 0 1
1 1 1
1 1 1
1 1 1
1 1 1
1 0 1
1 0 1
1 1 1
1 1 1
1 1 1
1 1 1
12
1

Explicatie

Traseul ilustrat are costul minim 12 si uneste elementul (2,3) de pe fata 2 cu elementul (2,2) de pe fata 5. Cealalta trapa de acces se afla pe fata 3, intr-o pozitie inaccesibila, deci numarul trapelor aflate la distanta minima fata de pozitia de start este 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content