RO Learner
a fost răspuns

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.


#3114

Răspuns :

CINEVAFARANUMERO

#include <fstream>

#include <cstring>

using namespace std;

int mat[202][202];

int matcpy[202][202];

struct ec{int x,y,p;};//element coada

ec coada[202*202];

void adaugavecini(ec x, int& k){

if(matcpy[x.x+1][x.y]==0){

coada[k].x = x.x+1;

coada[k].y = x.y;

coada[k].p=x.p+1;

k++;

matcpy[x.x+1][x.y]=1;

}

if(matcpy[x.x-1][x.y]==0){

coada[k].x = x.x-1;

coada[k].y = x.y;

coada[k].p = x.p+1;

k++;

matcpy[x.x-1][x.y]=1;

}

if(matcpy[x.x][x.y+1]==0){

coada[k].x = x.x;

coada[k].y = x.y+1;

coada[k].p = x.p+1;

k++;

matcpy[x.x][x.y+1]=1;

}

if(matcpy[x.x][x.y-1] == 0){

coada[k].x = x.x;

coada[k].y = x.y-1;

coada[k].p=x.p+1;

k++;

matcpy[x.x][x.y-1]=1;

}

}

int parcurgere(int x1, int y1, int x2, int y2){

int k = 0;

coada[k].x=x1,coada[k].y=y1,coada[k].p=1;

k++;

int kc = 0;

while(true){

int kc2=k;

for(int i = kc; i < kc2; i++){

adaugavecini(coada[i], k);

}

kc = kc2;

if(k == kc)return -1;

for(int i = kc; i < k; i++)

if(coada[i].x==x2&& coada[i].y == y2)return coada[i].p;

}

}

int main(){

ifstream fin("abq.in");

ofstream fout("abq.out");

int n,m,q;

char c;

fin>>n>>m;

for (int i = 0; i <= m+1; i++)

mat[0][i]= mat[n+1][i] = -1;

for(int i = 0; i <= n+1; i++)

mat[i][0] = mat[i][m+1] = -1;

for (int i = 1;i<=n;i++)

for(int j = 1;j<=m;j++){

fin>>c;

mat[i][j]= c=='a'?0:-1;

}

fin>>q;

int x1,y1,x2,y2;

for(int query=0;query<q;query++){

fin>>x1>>y1>>x2>>y2;

if(mat[x1][y1]==-1||mat[x2][y2]==-1){fout<<"-1\n";continue;}

memcpy(matcpy, mat, 202*202*4);

fout << parcurgere(x1,y1,x2,y2)<<'\n';

}

}

Daca ai nelamuriri intreaba-ma

Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că resursele disponibile v-au fost de ajutor. Pentru întrebări sau asistență suplimentară, nu ezitați să ne contactați. Ne bucurăm să vă revedem în curând și vă invităm să ne salvați în lista de site-uri preferate!


RO Learner: Alte intrebari