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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema abq:

// Prof. Nicu Vlad-Laurentiu
#include<fstream>
#define N 302
#define D 100002
#include<cstring>
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<strlen(ch);j++) v[i][j+1]=ch[j];
                       }
        fscanf(fin,"%d",&q);
        for (i=1;i<=q;i++)
        {
                fscanf(fin,"%d%d%d%d",&xi,&yi,&xf,&yf);
                if(v[xi][yi]=='b'||v[xf][yf]=='b') fout<<-1<<'\n';
                else if(v[xi][yi]=='a'){int k=lee(xi,yi,xf,yf);
                                     fout<<(k==0?-1:k+1)<<'\n';}
                else fout<<-1<<'\n';
        }
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3114 abq

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3114 abq de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3114 abq