Editsmart

Cerință

Se dă un text format din litere mici ale alfabetului și spații. Textul este așezat într-un caroiaj dreptunghiular cu $N$ rânduri și $N$ coloane, câte un caracter în fiecare poziție. Considerăm cuvânt o secvență maximală de litere aflate pe același rând, pe poziții consecutive.
Reguli pentru text:

• Nu există spații consecutive.
• Nu există spații la începutul sau la finalul unui rând.
• Toate rândurile sunt complete, inclusiv ultimul.

Poziția cursorului: Cursorul este întotdeauna poziționat pe un caracter (literă sau spațiu).

• La începutul rândului înseamnă pe primul caracter al acelui rând.
• La finalul rândului înseamnă pe ultimul caracter al acelui rând.

Cursorul se poate deplasa cu urmatoarele operatii, fiecare operație are costul 1:

1. Săgeți (stânga, dreapta, sus, jos): cursorul se deplasează cu un caracter în direcția respectivă.
2. Ctrl + Săgeată stânga/dreapta: cursorul se deplasează la începutul cuvântului anterior/următor de pe același rând.
3. Home: cursorul se deplasează la primul caracter de pe rândul curent.
4. End: cursorul se deplasează la ultimul caracter de pe rândul curent.

Condiții speciale pentru deplasarea cursorului:

• Dacă suntem la finalul rândului și apăsăm săgeata dreapta sau Ctrl + săgeata dreapta, cursorul rămâne pe loc.
• Dacă suntem la începutul rândului și apăsăm săgeata stânga sau Ctrl + săgeata stânga, cursorul rămâne pe loc.
• Dacă suntem pe orice caracter al unui cuvânt și apăsăm Ctrl + săgeata dreapta, ne deplasăm pe primul caracter al următorului cuvânt de pe același rând (dacă există). Altfel, cursorul rămâne pe loc.
• Dacă suntem pe primul caracter al unui cuvânt și apăsăm Ctrl + săgeata stânga, ne deplasăm pe primul caracter al cuvântului anterior (dacă există). Altfel, cursorul rămâne pe loc.
• Dacă suntem pe un caracter din interiorul unui cuvânt (nu primul) și apăsăm Ctrl + săgeata stânga, ne deplasăm pe primul caracter al acelui cuvânt.

Se cunoaște poziția inițială a cursorului și se dorește mutarea sa într-o poziție finală, cunoscută și ea, cu număr minim de operații.

Date de intrare

Fișierul editsmart.in conține pe prima linie un număr $N$ reprezentând dimensiunea matricei date (care este una pătratică). Pe fiecare dintre cele n linii se află câte n caractere care pot fi spații sau litere mici ale alfabetului. Pe următoarea linie se află $4$ numere $x_{start}, y_{start}, x_{end}, y_{end}$ reprezentând respectiv linia și coloana poziției inițiale a cursorului apoi linia și coloana poziției finale.

Date de ieșire

Fișierul editsmart.out va conține o valoare, reprezentând numărul minim de operații necesare deplasării cursorului din poziția inițială în poziția finală.

Restricții și precizări

• $3 \leq N \leq 1 \ 000$
• Pentru $24$ de puncte, $3 \leq N \leq 100$
• Pentru $12$ puncte, în textul dat nu se vor afla spații.
• Pentru $8$ puncte, poziția de început si poziția de final se vor afla pe aceeași linie.
• Pentru $5$ puncte, poziția de început si poziția de final se vor afla pe aceeași coloană.
• Pentru restul de $51$ de puncte, nu există restricții suplimentare.

Exemplu

editsmart.in

6
abc xy
a bc t
abcdef
abc pf
xbcdef
xbcdef
5 2 3 5

editsmart.out

3

Explicație

Plecăm din poziția $(5, 2)$. Cu o operație de tip săgeată sus ne ducem în poziția $(4, 2)$, acolo unde este caracterul b de pe rândul $4$. În continuare folosim operația Ctrl+săgeată dreapta și ne deplasăm pe caracterul p de pe poziția $(4, 5)$. În final, apăsăm săgeată sus din această poziție și ajungem în locul final.