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

Metoda Greedy este o metodă care poate fi uneori folosită în rezolvarea problemelor de următorul tip: Se dă o mulțime A. Să se determine o submulțime B a lui A astfel încât să fie îndeplinite anumite condiții – acestea depinzând de problema propriu-zisă.

Algoritm general

De regulă problema dată poate fi rezolvată prin mai multe metode, printre care și Greedy. O rezolvare generală de tip Greedy a problemei de mai sus este următoarea:

B ← ∅
terminat ← FALSE
Execută 
    Alege convenabil x ∈ A
    Dacă x poate fi adăugat în B Atunci
        B ← B ∪ {x}
    Altfel
        terminat ← TRUE
    SfârșitDacă
Cât timp terminat=FALSE

Altfel spus, pornim de la mulțimea vidă și adăugăm în mod repetat în B elemente până când acest lucru nu mai este posibil.

Observații

• stabilirea elementului care va fi adăugat în soluția B se face alegându-l pe cel mai bun din acel moment – este un optim local. Din acest motiv se numește Greedy (lacom);
• după adăugarea în soluția B a unui anumit element, acesta va rămâne în soluție până la final. Nu există un mecanism de revenire la la un pas anterior, precum la metoda Backtracking;
• alegerea optimului local nu duce întotdeauna la cea mai bună soluție B; metoda Greedy nu este întotdeauna corectă;
• schema prezentată mai sus este vagă și nu poate fi standardizată – să avem un algoritm detaliat care să poată fi aplicat de fiecare dată;
• sunt relativ puține probleme care pot fi rezolvate cu metoda Greedy;
• complexitatea metodei este de regulă polinomială – \( O(n^k)\), unde \(k\) este constant;
• folosim metoda Greedy în două situații:
  • știm sigur că rezolvarea este corectă (avem o demonstrație de natură matematică a corectitudinii);
  • nu avem decât soluții exponențiale (de tip Backtracking) și un algoritm Greedy dă o soluție nu neapărat optimă, dar acceptabilă.
• de regulă, înainte de începe alegerea elementelor convenabile din mulțimea A, elementele sale sunt ordonate după un criteriu specific, astfel încât alegerea optimului local să fie cât mai rapidă;

Există câteva probleme celebre de algoritmică ce pot fi rezolvate cu metoda Greedy:

• Problema spectacolelor
• Problema continuă a rucsacului
• Algoritmul lui Dijkstra pentru determinarea drumurilor de cost minim într-un graf
• Algoritmul lui Prim și Algoritmul lui Kruskal pentru determinarea arborelui parțial de cost minim al unui graf

Greedy euristic

Există probleme pentru care avem nevoie de o rezolvare acceptabilă, chiar dacă singurele soluții demonstrate corecte sunt exponențiale, de multe ori inutile în practică.

Putem să aplicăm pentru aceste probleme metoda Greedy, obținând soluții neoptime, dar suficient de apropiate de soluția optimă pentru a fi acceptabile. Mai mult, în implementarea algoritmului se pot aplica diverse artificii la alegerea optimului local care pot duce la soluții din ce în ce mai bune, deși nu neapărat optime.

Un algoritm care obține o soluție acceptabilă, deși nu neapărat optimă, se numește Greedy euristic.

O problemă cu o soluție euristică interesantă este Săritura calului1 (enunț modificat):

Se consideră o tablă de șah cu n linii și m coloane. La o poziție dată se află un cal de șah, acesta putându-se deplasa pe tablă în modul specific acestei piese de șah (în L). Să se determine o modalitate de parcurgere a tablei de către cal, astfel încât acesta să nu treacă de două ori prin aceeași poziție.

Pentru dimensiuni mici ale tablei se poate folosi metoda Backtracking, aceasta determinând o soluție optimă. Dacă dimensiunile tablei sunt mari, metoda Backtracking nu mai poate fi folosită. Putem încerca o strategie Greedy:

• plecăm de la poziția inițială, istart jstart
• cât timp este posibil
  • alegem o poziție vecină în L cu poziția curentă în care nu am mai fost
  • marcăm poziția aleasă într-un anumit mod și o considerăm poziție curentă

Succesul algoritmului Greedy stă în alegerea poziției vecine! Desigur, nu orice metodă duce la parcurgerea completă a tablei. Neexistând un mecanism de întoarcere la o stare anterioară, când nu mai găsim poziție vecină liberă pentru poziția curentă algoritmul se încheie.

O strategie de succes este să alegem pentru poziția curentă poziția vecină cel mai greu accesibilă la pasul următor – poziția vecină cu număr minim de vecini neparcurși. Teoretic, fiecare poziție de pe tablă are 8 poziții vecini, dar unele sunt în afara tablei, altele sunt deja parcurse, astfel că putem alege dintre cei 8 vecini ai poziției curente un vecin care la rândul său are număr minim de vecini neparcurși.

Mai mult, dacă există mai mulți vecini ai poziției curente cu număr minim de vecini neparcurși, putem varia vecinul cu care vom continua: primul găsit, ultimul găsit, cel mai de sus, cel mai de jos, îl alegem aleatoriu, etc., sporind șansele de a realiza o parcurgere completă a tablei.