== include(page="template/taskheader" task_id="matrice7") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $matrice7.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $matrice7.out$ ...
Î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.
h2. 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$
h2. Exemplu
table(example). |_. matrice7.in |_. matrice7.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5
.#..#
#..#.
.##.#
###.#
#...#
1 1 2 3| 7
|
h3. 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)
== include(page="template/taskfooter" task_id="matrice7") ==
