Cod sursa(job #553755)
#include<fstream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
ifstream fin("rj.in");
ofstream fout("rj.out");
const int di[] = { -1, -1, 0, 1, 1, 1, 0, -1 },
dj[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int n, m;
int ir, jr, ij, jj;
int v;
queue<pair<int, int> > Q;
char G[105][105];
int r[105][105];
int j[105][105];
void Read();
void BF( int x, int y );
void Solve();
bool OK( int i, int j);
void Write();
int main()
{
Read();
Solve();
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> n >> m;
fin.get();
char aux[101];
for( int i = 0; i < n; ++i )
{
fin.getline( aux, 101, '\n' );
strcpy( G[i], aux );
}
for( int i = 0; i < n; i++ )
for( int j2 = 0; j2 < m; j2++ )
{
if( G[i][j2] == 'R' )
{
ir = i;
jr = j2;
}
if( G[i][j2] == 'J' )
{
ij = i;
jj = j2;
}
r[i][j2] = j[i][j2] = INF;
}
}
void Solve()
{
v = 1;
BF( ir, jr );
v = 2;
BF( ij, jj );
Write();
}
void BF( int x, int y )
{
Q.push( make_pair( x, y ) );
if( v == 1 )
r[x][y] = 1;
else
j[x][y] = 1;
pair< int, int > p;
while( !Q.empty() )
{
p = Q.front();
for( int d = 0; d < 8; ++d )
{
int iv = p.first + di[d];
int jv = p.second + dj[d];
if( OK( iv, jv ) )
{
if( v == 1 && r[iv][jv] > r[ p.first ][ p.second ] + 1 )
{
r[iv][jv] = r[ p.first ][ p.second ] + 1;
Q.push( make_pair( iv, jv ) );
}
if( v != 1 && j[iv][jv] > j[ p.first ][ p.second ] )
{
j[iv][jv] = j[ p.first ][ p.second ] + 1;
Q.push( make_pair( iv, jv ) );
}
}
}
Q.pop();
}
}
bool OK( int i, int j )
{
if( i < 0 || i >= n || j < 0 || j >= m || G[i][j] == 'X' || G[i][j] == 'J' || G[i][j] == 'R' )
return false;
return true;
}
void Write()
{
int i1, j1, minim = INF;
for( int i = 0; i < n; ++i )
for( int j2 = 0; j2 < m; ++j2 )
if( j[i][j2] == r[i][j2] && minim > r[i][j2] )
{
i1 = i;
j1 = j2;
minim = r[i][j2];
}
fout << minim << ' '<< i1+1 << ' ' << j1+1;
}