Un lac are forma cubică, cu latura (număr natural). El este împărţit în poziţii elementare. O poziţie (o căsuţă) este identificată prin coordonatele , , , ca întru-un spaţiu tridimensional, unde:
- reprezintă nivelul ( pentru cel din imediata apropiere a suprafeţei apei, pentru nivelul de pe fundul lacului),
- reprezintă linia (linia este linia cea mai apropiată de privitor)
- reprezintă coloana (coloana este cea din stânga privitorului).
Exemplu pentru
Exemple de deplasări elementare:
- din poziţia (, , ) se poate ajunge la una din poziţiile: (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , );
- din poziţia (, , ) se poate ajunge în una din poziţiile: (, , ), (, , ), (, , ), (, , ).
Există o căsuţă specială, la suprafaţa apei, considerată pe nivelul ş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 la nivelelul , pentru ) şi care diferă ca linie şi coloană cu cel mult faţă de poziţia precedentă. Deci dintr-o poziţie se poate ajunge (vezi figura) în maxim poziţii pe nivelul imediat superior.
Scafandrul se află pe fundul lacului la coordonatele , , . El trebuie să ajungă la suprafaţa lacului (adică deasupra primului nivel al cubului), într-o poziţie de coordonate , , , adică imediat deasupra poziţiei , , 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 despărţite prin câte un spaţiu, reprezentând dimensiunea cubului, , linia şi coloana poziţiei de plecare, iar , linia şi coloana poziţiei de sosire;
- pe a doua linie numărul de staţii din lac;
- pe următoarele linii seturi de câte patru numere . Primele trei numere reprezintă coordonatele unei staţii iar ultimul număr 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 linii se vor scrie seturi de patru numere , 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 reprezintă punctul de plecare, iar ultima punctul de sosire (nivelul ).
Restricții și precizări
- 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 pentru numărul de mesaje (ca pentru o staţie cu 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