În ultima ecranizare a celebrei piese shakespeariene Romeo și Julieta trăiesc într-un oraș modern, comunică prin e-mail și chiar învață să programeze. Într-o secvență tulburătoare sunt prezentate frământările interioare ale celor doi eroi încercând fără succes să scrie un program care să determine un punct optim de întâlnire.
Ei au analizat harta orașului și au reprezentat-o sub forma unei matrice cu N linii şi M coloane, în matrice fiind marcate cu spațiu zonele prin care se poate trece (străzi lipsite de pericole) şi cu X zonele prin care nu se poate trece. De asemenea, în matrice au marcat cu R locul în care se află locuința lui Romeo, iar cu J locul în care se află locuința Julietei. Ei se pot deplasa numai prin zonele care sunt marcate cu spaţiu, din poziţia curentă în oricare dintre cele 8 poziţii învecinate (pe orizontală, verticală sau diagonale).
Cum lui Romeo nu îi place să aştepte şi nici să se lase aşteptat n-ar fi tocmai bine, ei au hotărât că trebuie să aleagă un punct de întâlnire în care atât Romeo, cât şi Julieta să poată ajunge în acelaşi timp, plecând de acasă. Fiindcă la întâlniri amândoi vin într-un suflet, ei estimează timpul necesar pentru a ajunge la întâlnire prin numărul de elemente din matrice care constituie drumul cel mai scurt de acasă până la punctul de întâlnire. Şi cum probabil există mai multe puncte de întâlnire posibile, ei vor să îl aleagă pe cel în care timpul necesar pentru a ajunge la punctul de întâlnire este minim.
Cerința
Scrieţi un program care să determine o poziţie pe hartă la care Romeo şi Julieta pot să ajungă în acelaşi timp. Dacă există mai multe soluţii, programul trebuie să determine o soluţie pentru care timpul este minim.
Date de intrare
Fișierul de intrare rj.in conține pe prima linie numerele naturale N M, care reprezintă numărul de linii şi respectiv de coloane ale matricei, separate prin spațiu, iar pe fiecare dintre următoarele N linii se află M caractere (care pot fi doar R, J, X sau spațiu) reprezentând matricea.
Date de ieșire
Fișierul de ieșire rj.out va conține o singură linie pe care sunt scrise trei numere naturale separate prin câte un spaţiu tmin x y, având semnificaţia:
x y reprezinţă punctul de întâlnire (x – numărul liniei, y – numărul coloanei);
tmin este timpul minim în care Romeo (respectiv Julieta) ajunge la punctul de întâlnire.
Restricții și precizări
1 < N, M < 101- Liniile şi coloanele matricei sunt numerotate începând cu
1. - Pentru datele de test există întotdeauna soluţie.
Exemplu
rj.in
5 8
XXR XXX
X X X
J X X X
XX
XXX XXXX
rj.out
4 4 4
Explicație
Traseul lui Romeo poate fi: (1,3), (2,4), (3,4), (4,4). Deci timpul necesar lui Romeo pentru a ajunge de acasă la punctul de întâlnire este 4. Traseul Julietei poate fi: (3,1), (4,2), (4,3), (4,5). Timpul necesar Julietei pentru a ajunge de acasă la punctul de întâlnire este de asemenea 4. În plus, 4 este punctul cel mai apropiat de ei cu această proprietate.
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 rj:
#include <fstream>
#define InFile "rj.in"
#define OutFile "rj.out"
#define NMax 102
#define NV 8
using namespace std;
int n, m, xr, yr, xj, yj;
int dl[NV]={0, 1, 0, -1, -1, 1, -1, 1};
int dc[NV]={1, 0, -1, 0, -1, 1, 1,-1};
char l[NMax][NMax];
int r[NMax][NMax];
void citire(void);
void afisare(int [NMax][NMax]);
void parcurge (int, int, int[NMax][NMax]);
int main()
{
int j[NMax][NMax];
citire();
parcurge(xr, yr, r);
parcurge(xj, yj, j);
afisare(j);
return 0;
}
void citire(void)
{
int i, k;
char c;
ifstream f(InFile);
f>>n>>m;
for (i=0; i<=n+1; i++) l[i][0]=l[i][m+1]='X';
for (i=0; i<=m+1; i++) l[0][i]=l[n+1][i]='X';
f.get(c);
for (i=1; i<=n; i++)
{for (k=1; k<=m; k++)
{f.get(c); l[i][k]=c;
if (l[i][k]=='R') {xr=i; yr=k; l[i][k]=' ';}
if (l[i][k]=='J') {xj=i; yj=k; l[i][k]=' ';}
}
f.get(c);}
f.close();
}
void parcurge (int x0, int y0, int d[NMax][NMax])
{
struct Punct {int l, c;} C[NMax*NMax], p;
int inc=0, sf=0, i, k;
for (i=0; i<=n+1; i++)
for (k=0; k<=m+1; k++) d[i][k]=-1;
C[0].l=x0; C[0].c=y0; d[x0][y0]=1;
while (inc<=sf)
{
p=C[inc++];
for (i=0; i<NV; i++)
if (l[p.l+dl[i]][p.c+dc[i]]==' ' && d[p.l+dl[i]][p.c+dc[i]]==-1)
{
d[p.l+dl[i]][p.c+dc[i]]=1+d[p.l][p.c];
C[++sf].l=p.l+dl[i];
C[sf].c=p.c+dc[i];
}
}
}
void afisare(int j[NMax][NMax])
{
ofstream f(OutFile);
int tmin=NMax*NMax+5, xmin=-1, ymin=-1, i, k;
for (i=1; i<=n; i++)
for (k=1; k<=m; k++)
if (r[i][k]==j[i][k])
if (r[i][k]<tmin && r[i][k]!=-1)
{tmin=r[i][k]; xmin=i; ymin=k;}
f<<tmin<<' '<<xmin<<' '<<ymin<<endl;
f.close();
}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 
.
Rezolvarea problemei #2390 rj
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2390 rj 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!