Pagini recente » Cod sursa (job #3227331) | Cod sursa (job #38050) | Cod sursa (job #2841263) | Cod sursa (job #2392154) | Cod sursa (job #3207712)
#include <cmath>
#include <fstream>
#include <stack>
#include <vector>
#include <cstring>
#include <queue>
#include <bitset>
#include <algorithm>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
#define maxi 101
int R[maxi][maxi],J[maxi][maxi];
int xr,yr,xj,yj,n,m;
char c[maxi];
bitset<maxi> a[maxi];
int xf,yf,tmin=2e9;
const int di[]={-1,-1,-1,0,0,1,1,1};
const int dj[]={-1,0,1,-1,1,-1,0,1};
void read()
{
cin>>n>>m;
cin.getline(c,1);
for(int i=1;i<=n;i++)
{
cin.getline(c,m+1);
for(int j=0;c[j];j++)
{
if(c[j]==' ')
a[i][j+1]=0;
else if(c[j]=='X')
a[i][j+1]=1;
else if(c[j]=='R')
xr=i,yr=j+1;
else if(c[j]=='J')
xj=i,yj=j+1;
}
}
}
bool inside(int i,int j){
return i>=1 && j>=1 && i<=n && j<=m;
}
void RomeoLEE()
{
queue< pair<int,int> > Q;
bitset<maxi> v[maxi];
Q.push({xr,yr});
v[xr][yr]=1;
R[xr][yr]=0;
while(!Q.empty())
{
int i=Q.front().first;
int j=Q.front().second;
for(int d=0;d<8;d++)
{
int ii=di[d]+i;
int jj=dj[d]+j;
if(inside(ii,jj) && a[ii][jj]==0 && v[ii][jj]==0)
{
R[ii][jj]=R[i][j]+1;
v[ii][jj]=1;
Q.push({ii,jj});
}
}
Q.pop();
}
}
void JulietaLEE()
{
queue< pair<int,int> > Q;
bitset<maxi> v[maxi];
Q.push({xj,yj});
v[xj][yj]=1;
J[xj][yj]=0;
while(!Q.empty())
{
int i=Q.front().first;
int j=Q.front().second;
for(int d=0;d<8;d++)
{
int ii=di[d]+i;
int jj=dj[d]+j;
if(inside(ii,jj) && a[ii][jj]==0 && v[ii][jj]==0)
{
J[ii][jj]=J[i][j]+1;
v[ii][jj]=1;
Q.push({ii,jj});
}
}
Q.pop();
}
}
void solve()
{
RomeoLEE();
JulietaLEE();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(R[i][j]==J[i][j] && tmin>R[i][j] && R[i][j]>0)
{
tmin=R[i][j];
xf=i,yf=j;
}
}
void print()
{
cout<<tmin+1<<' '<<xf<<' '<<yf;
}
int main()
{
read();
solve();
print();
return 0;
}