Fie o matrice cu n
linii (numerotate de la 1
la n
) și m
coloane (numerotate de la 1
la m
) ce conține doar literele a
și b
. Se definește un drum de la o poziție (xs, ys)
la o alta (xf, yf)
ca fiind o succesiune de pași care pornește din coordonatele (xs, ys)
și ajunge în (xf, yf)
și care trece numai prin componente care memorează litera a
. La fiecare pas, de la o poziţie (i, j)
se poate trece într-una din poziţiile (i+1, j)
, (i-1, j)
, (i, j+1)
, (i, j-1)
. Lungimea drumului este dată de numărul de componente care compun drumul.
Cerința
Având la dispoziție q
întrebări date sub forma a patru numere naturale xs ys xf yf
, trebuie să răspundeți pentru fiecare întrebare care este lungimea minimă a unui drum de la (xs, ys)
la (xf, yf)
care trece numai prin componente ce memorează litera a
. Dacă un astfel de drum nu există, veți afișa valoarea –1
.
Date de intrare
Fișierul de intrare abq.in
conține pe prima linie, separate prin spațiu, numerele n
și m
. Pe următoarele n
linii se găsesc câte m
caractere a
sau b
(neseparate de spații) și care definesc matricea. Pe linia n+2
se găsește numărul natural q
reprezentând numărul de întrebări, iar pe următoarele q
linii se află câte 4
numere naturale reprezentând o întrebare.
Date de ieșire
Fişierul abq.out
va avea exact q
linii. Pe linia i
se va afla un singur număr întreg reprezentând răspunsul la a i
-a întrebare.
Restricții și precizări
2 ≤ n,m ≤ 200
2 ≤ q ≤ 20
- Pentru 30% dintre teste,
n ≤ 50
Exemplu:
abq.in
3 4 abab aaab bbaa 4 1 1 2 3 1 2 2 3 1 1 3 4 3 3 3 4
abq.out
4 -1 6 2
Explicație
Pentru prima întrebare, 1 1 2 3
,
a
bab
aaa
b
bbaa
drumul este cel specificat și este compus din 4
caractere.
Pentru a doua întrebare, 1 2 2 3
,
ab
ab
aaab
bbaa
caracterul de început este b și de aceea se afișează -1.