Pagini recente » Cod sursa (job #1489730) | Cod sursa (job #1504989) | Cod sursa (job #2009697) | Cod sursa (job #1301960) | Cod sursa (job #2837569)
#include <iostream>
#include <queue>
#define MaxN 150
#define inf 1000000
using namespace std;
int n, m, xr,yr, xj,yj ;
char mat[MaxN][MaxN];
int distr[MaxN][MaxN];
int distj[MaxN][MaxN];
int dx[8]= {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8]= {0, 1, 1, 1, 0, -1, -1, -1};
bool verif(int x, int y)
{
return 0<x&& x<=n && 0<y&&y<=m;
}
void leer()
{
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
distr[i][j]=inf;
}
distr[xr][yr]=1;
queue<pair<int, int>>q;
q.push({xr, yr});
while(!q.empty())
{
xr=q.front().first;
yr=q.front().second;
q.pop();
for(int i=0; i<8; i++)
{
int xn=xr+dx[i];
int yn=yr+dy[i];
if(verif(xn, yn)&& mat[xn][yn]!='X'&& distr[xn][yn]>distr[xr][yr]+1)
{
distr[xn][yn]=1+distr[xr][yr];
q.push({xn, yn});
}
}
}
}
void leej()
{
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
distj[i][j]=inf;
}
distj[xj][yj]=1;
queue<pair<int, int>>q;
q.push({xj, yj});
while(!q.empty())
{
xj=q.front().first;
yj=q.front().second;
q.pop();
for(int i=0; i<8; i++)
{
int xn=xj+dx[i];
int yn=yj+dy[i];
if(verif(xn, yn)&& mat[xn][yn]!='X'&& distj[xn][yn]>distj[xj][yj]+1)
{
distj[xn][yn]=1+distj[xj][yj];
q.push({xn, yn});
}
}
}
}
int main()
{
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
cin >> n >> m;
cin.getline(mat[0], 150); // scap de \n de la final
for (int i = 1; i <= n; i++)
{
cin.getline(mat[i] + 1, 150);
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
if(mat[i][j]=='R')
{
xr=i;
yr=j;
}
if(mat[i][j]=='J')
{
xj=i;
yj=j;
}
}
leej();
leer();
int minim=inf;
int minx, miny;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
int maxim=max(distr[i][j], distj[i][j]);
if(maxim<minim)
{
minim=maxim;
minx=i;
miny=j;
}
}
}
cout<<minim<<" "<<minx<<" "<<miny;
return 0;
}