robot

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

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

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