Fişierul intrare/ieşire:	matrice7.in, matrice7.out	Sursă	ad-hoc
Autor	Adrian Budau	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.175 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Matrice7

Vi se da o matrice de N linii pe M coloane indexate de la 0 (liniile sunt de la 0 la N-1, iar coloanele de la 0 la M - 1). Matricea data este o harta, asta inseamana ca mergand in sus ajungeti din nou jos, de exemplu casuta (0, 0) are ca vecini pe casutele

• (0, 1) la dreapta
• (1, 0) in jos
• (N - 1, 0) in sus
• (0, M - 1) in stanga

Vi se mai spune si pentru fiecare casuta daca contine un obstacol sau nu. Vi se mai da un start si o destinatie. Vi se cere sa aflati numarul de casute pe drumul minim de la casuta de start la cea destinatie, acest drum neavand voie sa treaca prin niciun obstacol.

Date de intrare

Fişierul de intrare matrice7.in va contine pe prima linie N si M despartite printr-un spatiu.

Urmatoarele N linii vor contine M caracter (nedespartite prin nimic) . si #. . reprezinta casuta goala, iar # o casuta cu obstacol.

Ultima linie va contine 4 valori X1, Y1, X2 si Y2. X1 si Y1 reprezinta linia, respectiv coloana casutei de start, iar X2 si Y2 reprezinta linia, respectiv coloane casutei destinatie.

Date de ieşire

În fişierul de ieşire matrice7.out trebuie sa se afle pe primul si singurul rand o singura valoare reprezentand numarul de casute de pe drumul minim ce nu trece prin obstacole ce incepe la casuta de start si se termina la casuta destinatie.

Restricţii

• 5 ≤ N, M ≤ 1000
• Casuta de start si cea de destinatie sunt diferite si sunt amandoua libere (nu sunt casute obstacol)
• Exista intotdeauna solutie
• Pentru teste valorand 30% din punctajul maxim nu exista obstacole

Exemplu

Explicaţie

Unul din traseele minime este:

(1, 1) -> (1, 2) -> (0, 2) -> (0, 3) -> (4, 3) -> (3, 3) -> (2, 3)

Tot solutie este si:
(1, 1) -> (1, 2) -> (0, 2) -> (4, 2) -> (4, 3) -> (3, 3) -> (2, 3)

Cum se trimit solutii?