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ă.
Cerinţe
Scrieţi un program care determină:
- 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). - 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ă. - 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).
Date de intrare
Pe prima linie a fişierului robot.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.
Date de ieşire
Prima linie a fişierului robot.out conţine trei numere naturale, separate printr-un spaţiu, reprezentând răspunsurile la cele trei cerinţe.
Restrictii si precizări
1 ≤ n ≤ 1 000- Se garantează că robotul poate ajunge din poziţia
(L1, C1)în poziţia(L2, C2). - Pentru
30%din cazurin ≤ 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.
Exemplu
robot.in
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
robot.out
4 2 2
Explicaţie
Obstacolele care pot fi eliminate sunt cele de la 2, 4 si 3, 1