# PBinfo #3114 – abq – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț 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, abab aaab bbaa drumul este cel specificat ș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. ## Cod sursă C++ ```cpp // Prof. Nicu Vlad-Laurentiu #include #define N 302 #define D 100002 #include using namespace std; int a[N][N]; char v[N][N]; int m,n; //xi yi=pozitiile initial //xf,yf=pozitiile finale //m,n dimensiunile matricii const int dx[]={0,0,0,1,-1}; const int dy[]={0,1,-1,0,0}; //am presupus ca se poate merge in 4 directii: sus, jos, st,dr int cx[D],cy[D]; //coada int lee(int xi,int yi,int xf,int yf) { int f,b,x,y,xx,yy,i; memset(a,0,sizeof(a)); b=1; f=1; cx[f]=xi; cy[f]=yi; while (f<=b) { x=cx[f]; y=cy[f]; f++; for (i=1;i<=4;i++) { xx=x+dx[i]; yy=y+dy[i]; if (xx==xf&&yy==yf) return a[x][y]+1; //nu fac bordare si verific daca cooronatele se afla in matrice if (xx>0&&yy>0&&xx<=n&&yy<=m) { //verific daca locul respectiv e liber si daca casuta nu a mai fost vizitata if (v[xx][yy]=='a'&&a[xx][yy]==0) { a[xx][yy]=a[x][y]+1; b++; cx[b]=xx; cy[b]=yy; } } } } return a[xf][yf]; } int main() { int i,j,q,xi,yi,xf,yf; char ch[N+1]; FILE *fin=fopen("abq.in","rt"); ofstream fout("abq.out"); fscanf(fin,"%d%d",&n,&m); for (i=1;i<=n;i++) { fscanf(fin,"%s",ch); for (j=0;j