Scafandrul

Time limit: 0.1s Memory limit: 4MB Input: scafandrul.in Output: scafandrul.out

Un lac are forma cubică, cu latura MM (număr natural). El este împărţit în M3M^3 poziţii elementare. O poziţie (o căsuţă) este identificată prin coordonatele nn, ll, cc, ca întru-un spaţiu tridimensional, unde:

  • nn reprezintă nivelul (11 pentru cel din imediata apropiere a suprafeţei apei, MM pentru nivelul de pe fundul lacului),
  • ll reprezintă linia (linia 11 este linia cea mai apropiată de privitor)
  • cc reprezintă coloana (coloana 11 este cea din stânga privitorului).

Exemplu pentru m=4m = 4

Exemple de deplasări elementare:

  • din poziţia (44, 22, 22) se poate ajunge la una din poziţiile: (33, 11, 11), (33, 11, 22), (33, 11, 33), (33, 22, 11), (33, 22, 22), (33, 22, 33), (33, 33, 11), (33, 33, 22), (33, 33, 33);
  • din poziţia (22, 11, 11) se poate ajunge în una din poziţiile: (11, 11, 11), (11, 11, 22), (11, 22, 11), (11, 22, 22).

Există o căsuţă specială, la suprafaţa apei, considerată pe nivelul 00 şi anume cea în care trebuie să ajungă în final un scafandru ce pleacă de pe fundul lacului.

În lac există poziţii elementare considerate ca fiind staţii de lucru ce au de transmis la suprafaţă anumite mesaje. Aceste staţii pot fi oricâte şi pot fi dispuse oriunde în cub (chiar şi în poziţia de plecare a scafandrului).

Scafandrul se poate deplasa din poziţia sa numai într-o poziţie de pe nivelul imediat superior (de la nivelul ii la nivelelul i1i-1, pentru 1im1 \leq i \leq m) şi care diferă ca linie şi coloană cu cel mult 11 faţă de poziţia precedentă. Deci dintr-o poziţie se poate ajunge (vezi figura) în maxim 99 poziţii pe nivelul imediat superior.

Scafandrul se află pe fundul lacului la coordonatele mm, l1l_1, c1c_1. El trebuie să ajungă la suprafaţa lacului (adică deasupra primului nivel al cubului), într-o poziţie de coordonate 00, l2l_2, c2c_2, adică imediat deasupra poziţiei 11, l2l_2, c2c_2 din cub.

Cerinţa

Trebuie determinat ce drum trebuie să aleagă scafandrul pentru a duce la destinaţie cât mai multe mesaje, respectând restricţiile din enunţ.

Date de intrare

Fişierul de intrare scafandrul.in, conţine:

  • pe prima linie cinci numere m l1 c1 l2 c2m \ l_1 \ c_1 \ l_2 \ c_2 despărţite prin câte un spaţiu, reprezentând mm dimensiunea cubului, l1l_1, c1c_1 linia şi coloana poziţiei de plecare, iar l2l_2, c2c_2 linia şi coloana poziţiei de sosire;
  • pe a doua linie numărul yy de staţii din lac;
  • pe următoarele yy linii seturi de câte patru numere n l c pn \ l \ c \ p. Primele trei numere n l cn \ l \ c reprezintă coordonatele unei staţii iar ultimul număr pp reprezintă numărul de mesaje ce trebuiesc transmise de staţia respectivă;

Date de ieșire

Ieşirea se va face în fişierul scafandrul.out în formatul următor:

  • pe prima linie se va scrie numărul maxim de mesaje aduse la suprafaţă.
  • pe următoarele m+1m+1 linii se vor scrie seturi de patru numere n l c pn \ l \ c \ p, primele trei numere reprezentând coordonatele staţiilor vizitate (în ordinea parcurgerii), iar ultimul număr reprezentând numărul de mesaje culese din staţia respectivă.

Prima linie din cele m+1m+1 reprezintă punctul de plecare, iar ultima punctul de sosire (nivelul 00).

Restricții și precizări

  • 2M202 \leq M \leq 20
  • 0P1000 \leq P \leq 100
  • Nu este permisă ieşirea din lac decât prin punctul de sosire.
  • În punctul de sosire nu se află nici o staţie.
  • Dacă pentru o anumită pozitie toate mutările posibile sunt in căsuţe fără staţii, atunci se va scrie in fişierul de ieşire o linie cu coordonatele căsuţei alese şi valoarea 00 pentru numărul de mesaje (ca pentru o staţie cu 00 mesaje).

Exemplu

scafandrul.in

3 2 2 2 2
6
1 3 1 10
2 1 3 9
2 2 1 6
2 3 2 7
2 3 3 8
3 2 2 5

scafandrul.out

22
3 2 2 5
2 3 2 7
1 3 1 10
0 2 2 0

Log in or sign up to be able to send submissions!