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ţă

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).

Date de intrare

Pe prima linie a fişierului robot3.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 robot3.out conţine trei numere naturale, separate prin câte un spaţiu, reprezentând răspunsurile la cele trei cerinţe.

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.

Exemple

robot3.in	robot3.out	Explicaţii
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	Obstacolele care pot fi eliminate sunt cele de la 2,4 si 3,1

autor: Prof. Stelian Ciurea

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com