SIM1010 | Trambuline

Ești la o competiție de sărit pe trambulină. În cadrul ultimei probe, ai de parcurs un traseu în care trebuie să treci prin $P$ puncte de control într-o ordine anume, de la care vei colecta câte o ștampilă.

Traseul este de forma unui dreptunghi de dimensiuni $L \times C$ format din trambuline. Pentru a crește dificultatea traseului, în unele locuri organizatorii au scos trambulinele și au lăsat spații libere unde nu poți să aterizezi.

Inițial sari pe loc la punctul de start, numerotat $0$, iar după ce termini de adunat ștampilele trebuie să ajungi la punctul de finiș, numerotat $P+1$.

Deoarece o componentă importantă a acestei probe este stăpânirea controlul asupra mișcărilor tale, de fiecare dată când sari ai voie să îți lungești sau scurtezi săritura cu cel mult $1$, independent în ambele direcții (nord-sud și vest-est).

Poți considera că lungimea unei sărituri spre nord sau vest este reprezentată un număr pozitiv, iar spre sud sau est de un număr negativ. De exemplu, dacă te-ai deplasat cu $1$ spre sud la ultima săritură, la următoarea poți sări pe loc, cu $1$ spre sud, sau cu $2$ spre sud.

Cerință

Care este numărul minim de sărituri pe care trebuie să îl faci pentru a strânge toate ștampilele și a ajunge la poziția de finiș? Pentru a ajunge cu siguranță la poziția de finiș, trebuie ca ultima ta săritură să fie pe loc.

Date de intrare

Pe prima linie a fișierului de intrare trambuline.in se găsesc două numere $L$ și $C$, reprezentând lungimea și lățimea traseului.

Următoarele $L$ linii vor consta din $C$ caractere, # reprezentând o trambulină și . un spațiu liber.

Pe linia $L+1$ un număr $P$, reprezentând numărul de puncte de control de pe traseu.

Pe următoarele $P+2$ linii câte două numere $X$ și $Y$, reprezentând poziția de start, poziția celor $P$ puncte de control și a poziției de finiș.

Date de ieșire

Pe prima linie a fișierului de ieșire trambuline.out se va găsi numărul minim de sărituri necesare pentru terminarea traseului. Dacă acest lucru nu este posibil, afișați imposibil.

Restricții și precizări

• $1 \leq L, C \leq 50$;
• $1 \leq P \leq 5$;
• Pentru $0 \leq i \leq P+1$, $1 \leq X_i \leq L$ și $1 \leq Y_i \leq C$.

Exemplu

trambuline.in

5 5
#####
#...#
#####
#####
#.#.#
1
1 1
5 5
1 4

trambuline.out

9

Explicație