== include(page="template/taskheader" task_id="robot2") ==
Poveste şi cerinţă...
Un labirint este dat sub forma unui tablou pătratic cu $n × n$ elemente $0$ şi $1$, având semnificaţia: $0$ reprezintă poziţie liberă, iar $1$ poziţie ocupată. Un robot aflat în labirint, pe linia $L1$ şi coloana $C1$, trebuie să ajungă într-o poziţie finală de pe linia $L2$ şi coloana $C2$. Robotul se poate deplasa numai pe direcţiile orizontală şi verticală.
h2. Cerinţe
Scrieţi un program care determină:
**1)** Numărul minim de schimbări de direcţie pentru ca robotul să se deplaseze din poziţia $(L1, C1)$ în poziţia $(L2, C2)$.
**2)** Numărul minim de schimbări de direcţie pentru ca robotul să se deplaseze din poziţia $(L1, C1)$ în poziţia $(L2, C2)$, în situaţia în care putem transforma o singură poziţie ocupată într-o poziţie liberă.
**3)** Numărul de obstacole cu proprietatea că oricare dintre ele ar fi eliminate, se obţine numărul minim de schimbări de direcţie de la cerinţa 2).
h2. Date de intrare
Fişierul de intrare $robot2.in$ ...
Pe prima linie a fişierului $robot2.in$ se găseşte numărul natural $n$. Pe următoarele $n$ linii se află câte $n$ valori $0$ sau $1$ separate prin câte un spaţiu, reprezentând elementele labirintului. Pe linia $n+2$, sunt numerele $L1 C1 L2 C2$.
h2. Date de ieşire
În fişierul de ieşire $robot2.out$ ...
Prima linie a fişierului $robot2.out$ conţine trei numere naturale, separate printr-un spaţiu, reprezentând răspunsurile la cele trei cerinţe.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 1000$
* Se garantează că robotul poate ajunge din poziţia $(L1, C1)$ în poziţia $(L2, C2)$.
* Pentru $30%$ din cazuri $n ≤ 100$.
* Numerotarea liniilor şi a coloanelor începe de la $1$.
* Pentru rezolvarea corectă a primei cerinţe se acordă $20%$ din punctajul unui test. Pentru rezolvarea corectă a primelor două cerinţe se acordă $50%$ din punctajul unui test. Pentru rezolvarea corectă a tuturor celor trei cerinţe se acordă $100%$ din punctaj.
h2. Exemplu
table(example). |_. robot2.in |_. robot2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
0 1 1 0 0
0 0 0 1 0
1 0 1 1 0
0 0 0 1 0
0 0 0 0 0
1 1 1 5
| 4 2 2
|
h3. Explicaţie
...
Obstacolele care pot fi eliminate sunt cele de la $2,4$ si $3,1$.
== include(page="template/taskfooter" task_id="robot2") ==
