| abq |
|
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.Restricţii
Exemplu
|