Pagini recente » Cod sursa (job #1740643) | Cod sursa (job #1817536) | Cod sursa (job #2422876) | Cod sursa (job #1579005) | Cod sursa (job #1373085)
#include <iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
queue <int> qx;
queue <int> qy;
char h[102][102];
struct harta
{
int r,j;
}a[102][102];
void R_lee(int x,int y)
{
qx.push(x);
qy.push(y);
while(qx.empty()!=true)
{
x=qx.front();
y=qy.front();
if(a[x-1][y].r==-1||a[x-1][y].r>a[x][y].r+1){a[x-1][y].r=a[x][y].r+1; qx.push(x-1); qy.push(y);} //sus
if(a[x-1][y+1].r==-1||a[x-1][y+1].r>a[x][y].r+1){a[x-1][y+1].r=a[x][y].r+1; qx.push(x-1); qy.push(y+1);} //dreapta sus
if(a[x][y+1].r==-1||a[x][y+1].r>a[x][y].r+1){a[x][y+1].r=a[x][y].r+1; qx.push(x); qy.push(y+1);} //dreapta
if(a[x+1][y+1].r==-1||a[x+1][y+1].r>a[x][y].r+1){a[x+1][y+1].r=a[x][y].r+1; qx.push(x+1); qy.push(y+1);} //dreapta jos
if(a[x+1][y].r==-1||a[x+1][y].r>a[x][y].r+1){a[x+1][y].r=a[x][y].r+1; qx.push(x+1); qy.push(y);} //jos
if(a[x+1][y-1].r==-1||a[x+1][y-1].r>a[x][y].r+1){a[x+1][y-1].r=a[x][y].r+1; qx.push(x+1); qy.push(y-1);} //stanga jos
if(a[x][y-1].r==-1||a[x][y-1].r>a[x][y].r+1){a[x][y-1].r=a[x][y].r+1; qx.push(x); qy.push(y-1);} //stanga
if(a[x-1][y-1].r==-1||a[x-1][y-1].r>a[x][y].r+1){a[x-1][y-1].r=a[x][y].r+1; qx.push(x-1); qy.push(y-1);} //stanga sus
qx.pop(); qy.pop();
}
}
void J_lee(int x,int y)
{
qx.push(x);
qy.push(y);
while(qx.empty()!=true)
{
x=qx.front();
y=qy.front();
if(a[x-1][y].j==-1||a[x-1][y].j>a[x][y].j+1){a[x-1][y].j=a[x][y].j+1; qx.push(x-1); qy.push(y);} //sus
if(a[x-1][y+1].j==-1||a[x-1][y+1].j>a[x][y].j+1){a[x-1][y+1].j=a[x][y].j+1; qx.push(x-1); qy.push(y+1);} //dreapta sus
if(a[x][y+1].j==-1||a[x][y+1].j>a[x][y].j+1){a[x][y+1].j=a[x][y].j+1; qx.push(x); qy.push(y+1);} //dreapta
if(a[x+1][y+1].j==-1||a[x+1][y+1].j>a[x][y].j+1){a[x+1][y+1].j=a[x][y].j+1; qx.push(x+1); qy.push(y+1);} //dreapta jos
if(a[x+1][y].j==-1||a[x+1][y].j>a[x][y].j+1){a[x+1][y].j=a[x][y].j+1; qx.push(x+1); qy.push(y);} //jos
if(a[x+1][y-1].j==-1||a[x+1][y-1].j>a[x][y].j+1){a[x+1][y-1].j=a[x][y].j+1; qx.push(x+1); qy.push(y-1);} //stanga jos
if(a[x][y-1].j==-1||a[x][y-1].j>a[x][y].j+1){a[x][y-1].j=a[x][y].j+1; qx.push(x); qy.push(y-1);} //stanga
if(a[x-1][y-1].j==-1||a[x-1][y-1].j>a[x][y].j+1){a[x-1][y-1].j=a[x][y].j+1; qx.push(x-1); qy.push(y-1);} //stanga sus
qx.pop(); qy.pop();
}
}
void citire(int n)
{
int i;
for(i=1;i<=n;i++)
{
f.get();
f.get(h[i],102);
}
}
void transformare(int n,int m,int &xr,int &yr, int &xj, int &yj)
{
int i,k;
char c;
for(i=1;i<=n;i++)
for(k=0;k<m;k++)
{
c=h[i][k];
if(c==' '){a[i][k+1].r=-1; a[i][k+1].j=-1;}
else if(c=='X'){a[i][k+1].r=-2; a[i][k+1].j=-2;}
else if(c=='R'){a[i][k+1].r=0; a[i][k+1].r=1; xr=i; yr=k+1;}
else if(c=='J'){a[i][k+1].j=0; a[i][k+1].j=1; xj=i; yj=k+1;}
}
}
void solutie(int &tmin,int &solx,int &soly,int n,int m)
{
int i,k;
for(i=1;i<=n;i++)
for(k=1;k<=m;k++)
if(a[i][k].r<tmin&&a[i][k].r==a[i][k].j&&a[i][k].r>0){tmin=a[i][k].r; solx=i; soly=k;}
}
int main()
{
int n,m,tmin=32000,solx,soly,xr,yr,xj,yj;
f>>n>>m;
citire(n); // construim harta
transformare(n,m,xr,yr,xj,yj); // impartim harta celor doi
R_lee(xr,yr); // harta lui Romeo
J_lee(xj,yj); // harta Julietei
solutie(tmin,solx,soly,n,m); // punctul de intalnire
g<<tmin<<" "<<solx<<" "<<soly;
return 0;
}