Se citeste dimensiunea n a unei table de sah (n x n) si coordonatele (0-indexate) unei celule de start si ale unei celule destinatie. Determinati numarul minim de mutari ale calului necesare pentru a ajunge din celula de start in celula destinatie, folosind algoritmul Lee , unde vecinii unei celule sunt cele (cel mult 8) celule accesibile printr-o mutare de cal.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc x1, y1, x2, y2: linia si coloana celulei de start, apoi linia si coloana celulei destinatie.
- Date de iesire
- Se afiseaza numarul minim de mutari ale calului.
- Restrictii
- 1 <= n <= 30, 0 <= x1, y1, x2, y2 <= n - 1
Exemple
Exemplul 1
Intrare
8 0 0 7 7
Iesire
6
Exemplul 2
Intrare
8 0 0 1 2
Iesire
1