| Fişierul intrare/ieşire: | kdrum.in, kdrum.out | Sursă | Stelele Informaticii 2009, clasele 9-10 |
| Autor | Paul-Dan Baltescu | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kdrum
Laura este pasionata de plimbarile prin parc. Fiind totusi o activitate lipsita de originalitate, ea si-a propus ca plimbarile ei sa urmeze un plan mai nastrusnic. Pentru a va ajuta, ea a reprezentat parcul sub forma unei matrici cu N linii si M coloane. Pentru fiecare zona din parc, ea i-a atribuit un numar natural pozitiv dupa criterii numai de ea stiute. Zonele prin care nu poate trece le-a marcat cu 0. Acum ea se afla in pozitia x1 y1 si doreste sa ajunga la pozitia x2 y2 astfel incat produsul numerelor de pe drum sa fie divizibil cu un numar K. Pentru ca este frig afara, ea doreste sa stie care este lungimea minima a unui astfel de drum. Cum dorintele ei sunt porunci, voi trebuie sa o ajutati.
Date de intrare
Pe prima linie a fisierului de intrare kdrum.in se afla 3 numere intregi despartie prin spatiu: N M K. Pe urmatoarea linie se gasesc 4 numere intregi x1 y1 x2 y2. Urmatoarele N linii vor avea cate M numere despartite prin spatiu, simbolizand schema parcului.
Date de ieşire
În fişierul de ieşire kdrum.out se va afla un singur numar natural reprezentand lungimea minima a unui drum ce respecta proprietatile cerute.
Restricţii
- 1 ≤ N ≤ 50
- 1 ≤ M ≤ 50
- 1 ≤ K ≤ 12 000
- Elementele matricii sunt numere intregi cuprinse in intervalul [0, 100 000].
- Se garanteaza ca pozitiile de start si de final sunt valide.
- Se garanteaza ca exista cel putin un drum valid de la pozitia de start la destinatie.
- In 20% din teste, K = 1.
- Pentru 50% din teste, 1 ≤ K ≤ 200.
- Deplasarea se face in 4 directii: sus, jos, stanga, dreapta.
- Laura trebuie sa se deplaseze intr-o casuta vecina in fiecare moment de timp.
- Drumul Laurei poate trece de mai multe ori prin aceeasi pozitie, caz in care trebuie considerata de mai multe ori valoarea din acea zona.
Exemplu
| kdrum.in | kdrum.out |
|---|---|
| 3 3 6 1 1 3 3 1 3 5 1 0 2 6 1 1 | 5 |
Explicaţie
Cele doua solutii posibile sunt:
1 3 5
1 0 2
6 1 1
sau
1 3 5
1 0 2
6 1 1
Prima solutie are produsul numerelor de pe drum 6, in timp ce a doua are produsul 30. Ambele numere sunt divizibile cu 6.
