1334 afișări Stoica Mihnea Teodor (My_Life_Is_Not_Life) 16.11.2022 www.pbinfo.ro

Mihnea trăiește pe o planetă de dimensiunea n x n, cu linii și coloane enumerate de la 1 la n. Spunem că celula (l, c) este intersecția liniei l cu coloana c. Fiecare celulă de pe planetă este fie pământ, fie apă.

Pentru a-l ajuta pe Mihnea, intenționezi să creezi cel puțin un tunel. Tunelul îi va permite lui Mihnea să călătorească liber între cele două puncte extreme ale tunelului. Într-adevăr, crearea unui tunel este un efort mare: costul creării unui tunel între celulele (l1, c1) și (l2, c2) este (l1 – l2) ^ 2 + (c1 – c2) ^ 2.

Cerința

Pentru moment, sarcina ta este să găsești costul minim de a crea câteva tuneluri astfel încât Mihnea să poată călători de la (l1,c1) la (l2,c2). Dacă nu trebuie creat niciun tunel, costul este 0.

Date de intrare

In fisierul de intrare mihneapolis.in, prima linie conține un număr întreg n (1 ≤ n ≤ 50) — dimensiunea planetei.
A doua linie conține două numere întregi separate prin spațiu l1 și c1 (1 ≤ l1, c1 ≤ n) – indicând celula în care locuiește Mihnea.
A treia linie conține două numere întregi separate prin spațiu l2 și c2 (1 ≤ l2, c2 ≤ n) – indicând celula în care Mihnea dorește să meargă.
Fiecare dintre următoarele n linii conține un șir de n caractere. Al j-lea caracter de pe linia i reprezintă tipul de celulă de la coordonata (i, j) (1 este teren, 0 este apă).
Este garantat că (l1, c1) și (l2, c2) sunt celule de teren.

Date de ieșire

In fișierul mihneapolis.out, afișați un număr întreg care reprezintă costul minim de creare a câteva tuneluri, astfel încât Mihnea să poată călători de la (l1,c1) la (l2,c2).

Exemplu

mihneapolis.in

5
1 1
5 5
00001
11111
00111
00110
00110

mihneapolis.out

10

Problemă propusă de @My_Life_Is_Not_Life și @mateiUNU


1334 afișări Stoica Mihnea Teodor (My_Life_Is_Not_Life) 16.11.2022 www.pbinfo.ro