Pagini recente » Cod sursa (job #1961915) | Cod sursa (job #83643) | Cod sursa (job #2592368) | Cod sursa (job #1247024) | Cod sursa (job #1825664)
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
queue < pair < int, int > > r;
queue < pair < int, int > > ju;
int di[8]={1,-1,0,0,-1,-1,1,1};
int dj[8]={0,0,1,-1,-1,1,-1,1};
int romeo[101][101];
int julieta[101][101];
string costel;
int n,m,startxr,startyr,finalxr,finalyr;
int startxj,startyj,finalxj,finalyj;
bool okr (int i, int j)
{
if (i<1 || i>n || j<1 || j>m || romeo[i][j]==-1) return 0;
return 1;
}
bool okj (int i, int j)
{
if (i<1 || i>n || j<1 || j>m || julieta[i][j]==-1) return 0;
return 1;
}
void leeromeo()
{
int i,j,vecini,vecinj;
romeo[startxr][startyr]=1;
r.push(make_pair(startxr,startyr));
while (!r.empty())
{
i=r.front().first;
j=r.front().second;
r.pop();
for (int k=0;k<8;k++)
{
vecini=i+di[k];
vecinj=j+dj[k];
if (okr(vecini,vecinj) && romeo[vecini][vecinj] < 1)
{
r.push(make_pair(vecini,vecinj));
romeo[vecini][vecinj]=romeo[i][j]+1;
}
}
}
}
void leejulieta()
{
int i,j,vecini,vecinj;
julieta[startxj][startyj]=1;
ju.push(make_pair(startxj,startyj));
while (!ju.empty())
{
i=ju.front().first;
j=ju.front().second;
ju.pop();
for (int k=0;k<8;k++)
{
vecini=i+di[k];
vecinj=j+dj[k];
if (okj(vecini,vecinj) && julieta[vecini][vecinj]<1)
{
ju.push(make_pair(vecini,vecinj));
julieta[vecini][vecinj]=julieta[i][j]+1;
}
}
}
}
int main ()
{
fin >> n >> m;
getline(fin,costel,'\n');
for (int i=1;i<=n;i++)
{
getline(fin,costel,'\n');
for (int j=0;j<(int)costel.size();j++)
{
if (costel[j]=='X') {romeo[i][j+1]=-1; julieta[i][j+1]=-1;}
else if (costel[j]=='R') {startxr=i;startyr=j+1;}
else if (costel[j]=='J') {startxj=i;startyj=j+1;}
}
}
leejulieta();
leeromeo();
int finalx=0,finaly=0;
int tmin=10005;
for (int linie=1;linie<=n;linie++)
for (int col=1;col<=m;col++)
{
if (romeo[linie][col]==julieta[linie][col] && romeo[linie][col]<tmin && romeo[linie][col]>0)
{
tmin=romeo[linie][col];
finalx=linie;
finaly=col;
}
}
fout << tmin << " "<< finalx << " " << finaly << "\n";
}