Fişierul intrare/ieşire:kdrum.in, kdrum.outSursăStelele Informaticii 2009, clasele 9-10
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inkdrum.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content