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 ≤ 1 000 000
• Elementele matricii sunt numere intregi cuprinse in intervalul [0, 10 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.
• Pentru 50% din teste, 1 ≤ K ≤ 200.

Exemplu

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.

Cum se trimit solutii?