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 dintre 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ţă
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 drumul de lungime minimă 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 naturale n şi m. Pe următoarele n linii se găsesc câte m caractere din mulţimea {'a', 'b'} (neseparate de spaţii) şi care reprezintă matricea. Pe linia n+2 se găseşte numărul natural q reprezentând numărul de întrebări, iar pe fiecare dintre următoarele q linii se află câte 4 numere naturale reprezentând o întrebare.
Date de ieşire
Fişierul de ieşire 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.
Pentru prima întrebare, 1 1 2 3, abab aaab
bbaa
drumul este cel îngroşat şi este compus din 4 caractere.
Pentru a doua întrebare, 1 2 2 3,
abab
aaab
bbaa
caracterul de început este b şi de aceea se afişează -1