Pagini recente » Cod sursa (job #682665) | Cod sursa (job #1953208) | Cod sursa (job #512039) | Rating radu ion (xxxx) | Cod sursa (job #902474)
Cod sursa(job #902474)
#include<fstream>
#define ff first
#define ss second
#include<queue>
#include <algorithm>
#define mkp make_pair
#define punct pair<int,int>
using namespace std;
punct startr,startj;
const int dx[]={0, 1, 0, -1, -1, 1, -1, 1};
const int dy[]={1, 0, -1, 0, -1, 1, 1,-1};
ofstream fout("rj.out");
int A[101][101],Dr[150][150],Dj[150][150],m,n,i;
void lee();
void citire()
{
char x[255];
int j;
ifstream fin("rj.in");
fin>>n>>m;
fin.getline(x,255);
for(i=1;i<=n;i++)
{
fin.getline(x,255);
for(j=0;j<m;j++)
{
if(x[j]==' ')
A[i][j]=0;
else
if(x[j]=='R')
{
startr.ff=i;
startr.ss=j;
A[i][j]=1;
}
else
if(x[j]=='J')
{
startj.ff=i;
startj.ss=j;
A[i][j]=1;
}
else
A[i][j]=-1;
}
}
}
void initializare();
void initializare()
{
for(i=1;i<=n;i++)
for(int j=0;j<m;j++)
{
Dr[i][j]=-1;
Dj[i][j]=-1;
}
for (int i=0; i<=n+1; i++) A[i][-1]=A[i][m]=-1;
for (int i=0; i<=m; i++) A[0][i]=A[n+1][i]=-1;
Dr[startr.ff][startr.ss]=1;
Dj[startj.ff][startj.ss]=1;
}
int afara(int linie, int col)
{
return A[linie][col]!=-1;
}
void lee()
{
initializare();
queue<punct> R;
queue<punct> J;
punct now,now2;
R.push(startr);
while (R.empty()==false)
{
now=R.front();R.pop();
for (i = 0; i < 8; ++i)
{
now2 = mkp(now.ff + dx[i], now.ss + dy[i]);
if (afara(now2.ff,now2.ss)==1 && Dr[now2.ff][now2.ss]==-1&&A[now2.ff][now2.ss]==0)
{
Dr[now2.ff][now2.ss] = Dr[now.ff][now.ss] + 1;
R.push(now2);
}
}
}
J.push(startj);
while (J.empty()==false)
{
now=J.front();J.pop();
for (i = 0; i < 8; ++i)
{
now2 = mkp(now.ff + dx[i], now.ss + dy[i]);
if (afara(now2.ff,now2.ss)==1 && Dj[now2.ff][now2.ss]==-1&&A[now2.ff][now2.ss]==0)
{
Dj[now2.ff][now2.ss] = Dj[now.ff][now.ss] + 1;
J.push(now2);
}
}
}
}
int main ()
{
citire();
lee();
int tmin=2000000,xmin,ymin,j,i;
for(i=1;i<=n;i++)
for(j=0;j<m;j++)
{
if(Dj[i][j]==Dr[i][j])
{
if (Dr[i][j]<tmin && Dr[i][j]!=-1)
{
tmin=Dr[i][j];
xmin=i;
ymin=j;
}
}
}
fout<<tmin<<" "<<xmin<<" "<<ymin+1;
}