#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;
const int dx[8]={0, 1, 0, -1, -1, 1, -1, 1};
const int dy[8]={1, 0, -1, 0, -1, 1, 1,-1};
struct Point
{
int x, y, i, j;
Point(int x = 0, int y = 0, int i = 0, int j = 0) : x(x), y(y), i(i), j(j) {};
void set(int x = 0, int y = 0, int i = 0, int j = 0) {this->x = x; this->y = y; this->i = i; this->j = j;}
};
char **read(int *n, int *m)
{
FILE *f = fopen("rj.in", "r");
char **map = NULL;
int i, j;
fscanf(f, "%i%i", n, m);
map = new char*[*n];
for (i = 0; i<*n; ++i)
map[i] = new char[*m];
for (i=0; i<*n; ++i)
for (j=0; j<*m; ++j)
while ((map[i][j] = fgetc(f)) == '\n');
fclose(f);
return map;
}
void _findPath(char **map, int &n, int &m, Point start, Point &end, int &step, Point *pathTemp, queue<Point*> &path)
{
if (start.x < 0 || start.x > n-1 || start.y < 0 || start.y > m - 1)
return;
char c = map[start.x][start.y];
if (c == ' ' || c == 'R' || c == 'J')
{
map[start.x][start.y] = 'X';
pathTemp[step++].set(start.x, start.y, step > 0 ? pathTemp[step-1].i + start.x : start.x, step > 0 ? pathTemp[step-1].j + start.y : start.y);
if (start.x == end.x && start.y == end.y && (path.size() > step || path.empty() || (path.size() == step && path.back()->i > pathTemp[step-1].i) ||
(path.size() == step && path.back()->i == pathTemp[step-1].i && path.back()->j > pathTemp[step-1].j)))
{
while (!path.empty())
{
delete path.front();
path.pop();
}
for (int i=0; i<step; ++i)
path.push(new Point(pathTemp[i].x, pathTemp[i].y, pathTemp[i].i, pathTemp[i].j));
}
else
for (int i = 0; i < 8; ++i)
_findPath(map, n, m, Point(start.x + dx[i], start.y + dy[i]), end, step, pathTemp, path);
map[start.x][start.y] = c;
--step;
}
}
void findPath(char **map, int n, int m)
{
queue<Point*> pathF;
Point *pathTemp = new Point[n*m], *best = NULL;;
Point romeo(-1, -1), juliet(-1, -1);
int i, j, tmin, x, y;
bool even = false;
for (i=0; i<n; ++i)
for (j=0; j<m; ++j)
{
if (map[i][j] == 'R')
romeo.set(i, j);
else if (map[i][j] == 'J')
juliet.set(i, j);
}
i = 0;
_findPath(map, n, m, romeo, juliet, i, pathTemp, pathF);
if ((pathF.size() & 1) == 0) even = true;
tmin = (pathF.size() / 2) + (even ? 0 : 1);
j = (pathF.size() / 2) + (even ? -1 : 0);
for (i = 0; i < j; ++i)
pathF.pop();
best = pathF.front();
pathF.pop();
if (even && (best->x > pathF.front()->x || (best->x == pathF.front()->x && best->y > pathF.front()->y)))
best = pathF.front();
FILE *f = fopen("rj.out", "w");
fprintf(f, "%i %i %i", tmin, best->x+1, best->y+1);
fclose(f);
}
int main()
{
char **map = NULL;
int n = 0, m = 0;
map = read(&n, &m);
findPath(map, n, m);
return 0;
}