traseu3

Traseu3

* $2 ≤ N ≤ 100$ ; $1 ≤ M ≤ 5000$ şi $M < N*N-2$
* Şoricelul nu intră decât în camere neocupate de clienţi.
* Camera şoricelului este o cameră neocupată de clienţi.

* Dacă există mai multe trasee ale şoricelului de la camera lui la camera de alimente care trec prin exact $T$ camere,
atunci traseul afişat va fi cel mai mic traseu din punct de vedere lexicografic.
* Eticheta $(X1 Y1 Z1)$ se consideră strict mai mică în sens lexicografic ca eticheta $(X2 Y2 Z2)$ dacă este satisfăcută
doar una dintre condiţiile:

* Dacă există mai multe trasee ale şoricelului de la camera lui la camera de alimente care trec prin exact $T$ camere, atunci traseul afişat va fi cel mai mic traseu din punct de vedere lexicografic.
* Eticheta $(X1 Y1 Z1)$ se consideră strict mai mică în sens lexicografic ca eticheta $(X2 Y2 Z2)$ dacă este satisfăcută doar una dintre condiţiile:

1) $X1 < X2$ 2) $X1 = X2$ şi $Y1 < Y2$ 3) $X1 = X2$ şi $Y1 = Y2$ şi $Z1 < Z2$

* Eticheta $X1 Y1 Z1$ se consideră egală cu eticheta $X2 Y2 Z2$ dacă $X1 = X2$ şi $Y1 = Y2$ şi $Z1 = Z2$. Vom scrie
egalitatea lor astfel: $(X1 Y1 Z1) = (X2 Y2 Z2)$.
* Traseul ce trece (în această ordine) prin camerele cu etichetele $(X1 Y1 Z1), (X2 Y2 Z2),..., (XT YT ZT)$
este mai mic din punct de vedere lexicografic ca traseul $(A1 B1 C1, A2 B2 C2,…, AT BT CT)$ dacă există un indice
$J$ (1 ≤ J ≤ T) astfel încât $(X1 Y1 Z1) = (A1 B1 C1), (X2 Y2 Z2) = (A2 B2 C2)…., (XJ-1 YJ-1 ZJ-1) = (AJ-1 BJ-1 CJ-1)$ iar
eticheta $(XJ YJ ZJ)$ este strict mai mică ca eticheta $(AJ BJ CJ)$.
* Se acordă: 40% din punctaj pentru determinarea corectă a numărului $T$ şi 100% din punctaj pentru rezolvarea
corectă a ambelor cerinţe.

* Eticheta $X1 Y1 Z1$ se consideră egală cu eticheta $X2 Y2 Z2$ dacă $X1 = X2$ şi $Y1 = Y2$ şi $Z1 = Z2$. Vom scrie egalitatea lor astfel: $(X1 Y1 Z1) = (X2 Y2 Z2)$.
* Traseul ce trece (în această ordine) prin camerele cu etichetele $(X1 Y1 Z1), (X2 Y2 Z2),..., (XT YT ZT)$ este mai mic din punct de vedere lexicografic ca traseul $(A1 B1 C1, A2 B2 C2,…, AT BT CT)$ dacă există un indice $J$ (1 ≤ J ≤ T) astfel încât $(X1 Y1 Z1) = (A1 B1 C1), (X2 Y2 Z2) = (A2 B2 C2)…., (XJ-1 YJ-1 ZJ-1) = (AJ-1 BJ-1 CJ-1)$ iar eticheta $(XJ YJ ZJ)$ este strict mai mică ca eticheta $(AJ BJ CJ)$.
* Se acordă: 40% din punctaj pentru determinarea corectă a numărului $T$ şi 100% din punctaj pentru rezolvarea corectă a ambelor cerinţe.

* Se garantează că există soluţie pentru ambele cerinţe, pentru toate datele de test.
h2. Exemplu

table(example). |_. traseu3.in |_. traseu3.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. traseu3.in |_. traseu3.out |_. Explicaţie|
| 3 4
1 1 1
3 3 3
3 3 1
2 1 1
3 1 1
3 1 3
| 7
1 1 1
1 1 2
1 1 3
1 2 3
1 3 3
2 3 3
3 3 3
| !problema/traseu3?traseu4.png!
|

h3. Explicaţie

...

Hotelul are trei etaje (1,2 şi 3). Pe fiecare etaj sunt 3*3 camere. Şoricelul se află în camera cu eticheta $1 1 1$ iar camera cu alimente are eticheta $3 3 3.$
Sunt 4 camere ocupate de clienţi. Acestea au etichetele : $3 3 1, 2 1 1, 3 1 1, 3 1 3.$
Traseul cel mai scurt trece prin $T=7$ camere.
Sunt mai multe astfel de trasee. De exemplu:
$1) (1 1 1, 1 1 2, 1 1 3, 1 2 3, 1 3 3, 2 3 3, 3 3 3)$
$2) (1 1 1, 1 1 2, 1 1 3, 2 1 3, 2 2 3, 3 2 3, 3 3 3)$
$3) (1 1 1, 1 2 1, 1 3 1, 1 3 2, 2 3 2, 3 2 3, 3 3 3)$
etc.
Cel mai mic astfel de traseu (în sens lexicografic) este traseul 1).

== include(page="template/taskfooter" task_id="traseu3") ==

9931