Pagini recente » Cod sursa (job #2468493) | Cod sursa (job #3158146) | Cod sursa (job #2848399) | Cod sursa (job #313390) | Cod sursa (job #577901)
Cod sursa(job #577901)
#include<fstream>
#define L 102
using namespace std;
void initializare();
void citeste();
void rezolva();
void afiseaza();
void lee(int a[L][L], int, int);
int m,n;//numarul de linii si coloane
int ro[L][L],ju[L][L];//matricile lui romeo si julieta
int xri,yri,xji,yji;//pozitiile initiale ale lui romeo si julieta
int sol, iaux, jaux;//solutia si pozitia ei
int dx[]={0,1,-1,0,0,-1,1,1,-1};//directiile pe linie
int dy[]={0,0,0,1,-1,-1,1,-1,1};//directiile pe coloana
struct coada {int x,y;};
coada c[L*L];
void initializare()
{
for(int i=0;i<L;i++)
for(int j=0;j<L;j++)
ro[i][j]=ju[i][j]=-2;//umplu matricile cu -2 (se poate trece)
for(int i=0;i<=m+1;i++) ro[i][0]=ro[i][n+1]=ju[i][0]=ju[i][n+1]=-1;//bordare verticala
for(int i=0;i<=n+1;i++) ro[0][i]=ro[m+1][i]=ju[0][i]=ju[m+1][i]=-1;//bordare orizontala
}
void citeste()
{
char s[L+2];
int i,j;
ifstream fin ("rj.in");
fin>>m>>n;//citesc nr de linii si coloane
fin.get();//citesc spatiul ramas
initializare();//initializez matricile
for(i=1;i<=m;i++)
{
fin.getline(s,102);//citesc linia i in sirul de caractere s
for( j=0;j<n;j++) //parcurg sirul s de la 0
{
if(s[j]=='X') ro[i][j+1]=ju[i][j+1]=-1;//onstacol
else if(s[j]=='R') xri=i, yri=j+1;//pozitia lui romeo
else if (s[j]=='J') xji=i, yji=j+1;//pozitia julietei
}
}
fin.close();
}
void rezolva()
{
lee(ro,xri,yri);//alg lui lee pt romeo
lee(ju,xji,yji);//alg lui lee pt julieta
sol=L*L+1;//punctul de intalnire comun minim
for(int i=1;i<=m;i++)
for(int j=1;j<=n+1;j++)
if(ro[i][j]==ju[i][j] && ro[i][j]>1)
if(ro[i][j]<sol) {sol=ro[i][j];iaux=i;jaux=j;}//daca am gasit un punct de intalnire minim il salvez
}
void lee(int a[L][L],int xi,int yi)
{
int xc,yc,mc,x2,y2,i;
int p,u;
p=u=1;//coada are initial o singura pozitie - cea de start
c[p].x=xi;// pun pozitia pe axa x in coada
c[p].y=yi;//pun pozitia pe axa y in coada
a[xi][yi]=1;//pozitia de plecare
while(p<=u)//cat timp nu am ajuns la sfarsitul cozii
{
xc=c[p].x;//x curent
yc=c[p].y;//y curent
mc=a[xc][yc];//marcajul(pasul) curent
for(i=1;i<=8;i++) //iau cele 8 directii
{
x2=xc+dx[i];
y2=yc+dy[i];
if(a[x2][y2]==-2)//daca se poate trece(e liber)
{
u++;//maresc coada
c[u].x=x2;//adaug noua pozitie in coada
c[u].y=y2;
a[x2][y2]=mc+1;//am facut numarul de pasi anteriori + 1
}
}
p++;//incrementez p (trec la urmatorul element din coada)
}
}
void afiseaza()
{
ofstream fout("rj.out");
fout<<sol<<" "<<iaux<<" "<<jaux;//afisez solutia si pozitia unde am gasit-o
fout.close();
}
int main()
{
citeste();
rezolva();
afiseaza();
return 0;
}