#include <cstdio>
#include <queue>
#include <climits>
using namespace std;
const int INF_INT = INT_MAX;
const char INF_CHAR = SCHAR_MAX;
struct coord
{
int i, j;
bool operator!= (const coord& dp)
{
if (i != dp.i || j != dp.j)
return true;
return false;
}
bool operator== (coord& dp)
{
if (i == dp.i && j == dp.j)
return true;
return false;
}
bool is_neighbour (coord& dp)
{
if (i == INF_INT || j == INF_INT)
return false;
coord temp;
coord NO_NEIGH = {INF_INT, INF_INT};
extern coord (get_neighbour) (const coord&);
while ((temp = _get_neighbour()) != NO_NEIGH)
if (temp == dp)
return true;
return false;
}
coord _get_neighbour()
{
static int vis_neighbours = 0;
if (vis_neighbours == 8)
{
vis_neighbours = 0;
return {INF_INT, INF_INT};
}
extern bool e_valid(int, int);
vis_neighbours++;
switch(vis_neighbours)
{
case 1: if (e_valid(i + 1, j - 1)) return {i + 1, j - 1}; else return {-1, -1};
case 2: if (e_valid(i, j - 1)) return {i, j - 1}; else return {-1, -1};
case 3: if (e_valid(i - 1, j - 1)) return {i - 1, j - 1}; else return {-1, -1};
case 4: if (e_valid(i + 1, j)) return {i + 1, j}; else return {-1, -1};
case 5: if (e_valid(i - 1, j)) return {i - 1, j}; else return {-1, -1};
case 6: if (e_valid(i + 1, j + 1)) return {i + 1, j + 1}; else return {-1, -1};
case 7: if (e_valid(i, j + 1)) return {i, j + 1}; else return {-1, -1};
case 8: if (e_valid(i - 1, j + 1)) return {i - 1, j + 1};
default: vis_neighbours = 0; return {INF_INT, INF_INT};
}
}
}R, J;
const coord NO_NEIGH = {INF_INT, INF_INT}, NOT_YET = {-1, -1};
int nr_col, nr_linii;
char **m_city;
bool e_valid (int i, int j)
{
if (i < 0 || i >= nr_linii || j < 0 || j >= nr_col || m_city[i][j] == 0)
return 0;
return 1;
}
coord get_neighbour(const coord& curr)
{
static int vis_neighbours = 0;
if (vis_neighbours == 8)
{
vis_neighbours = 0;
return NO_NEIGH;
}
vis_neighbours++;
switch(vis_neighbours)
{
case 1: if (e_valid(curr.i + 1, curr.j - 1)) return {curr.i + 1, curr.j - 1}; else return NOT_YET;
case 2: if (e_valid(curr.i, curr.j - 1)) return {curr.i, curr.j - 1}; else return NOT_YET;
case 3: if (e_valid(curr.i - 1, curr.j - 1)) return {curr.i - 1, curr.j - 1}; else return NOT_YET;
case 4: if (e_valid(curr.i + 1, curr.j)) return {curr.i + 1, curr.j}; else return NOT_YET;
case 5: if (e_valid(curr.i - 1, curr.j)) return {curr.i - 1, curr.j}; else return NOT_YET;
case 6: if (e_valid(curr.i + 1, curr.j + 1)) return {curr.i + 1, curr.j + 1}; else return NOT_YET;
case 7: if (e_valid(curr.i, curr.j + 1)) return {curr.i, curr.j + 1}; else return NOT_YET;
case 8: if (e_valid(curr.i - 1, curr.j + 1)) return {curr.i - 1, curr.j + 1};
default: vis_neighbours = 0; return NO_NEIGH;
}
}
void citesc_date(const char* t)
{
FILE *f = fopen(t, "r");
fscanf(f, "%d %d", &nr_linii, &nr_col);
m_city = new char*[nr_linii];
for (int i = 0; i < nr_linii; i++)
m_city[i] = new char[nr_col];
fscanf(f, "%*c");
char c[101];
for (int i = 0; i < nr_linii; i++)
{
fgets(c, 102, f);
for (int j = 0; j < nr_col; j++)
{
if (c[j] == 'R')
{
m_city[i][j] = 1;
R.i = i;
R.j = j;
}
else if (c[j] == 'J')
{
m_city[i][j] = 1;
J.i = i;
J.j = j;
}
else if (c[j] == ' ')
m_city[i][j] = 1;
else if (c[j] == 'X')
m_city[i][j] = 0;
}
}
fclose(f);
}
void BFS(char ** &m_dist, coord ** &m_parrent)
{
queue <coord> Q;
m_dist = new char* [nr_linii];
m_parrent = new coord* [nr_linii];
for (int i = 0; i < nr_linii; i++)
{
m_dist[i] = new char [nr_col];
m_parrent[i] = new coord [nr_col];
for (int j = 0; j < nr_col; j++)
m_dist[i][j] = INF_CHAR;
}
m_dist[R.i][R.j] = 0;
m_parrent[R.i][R.j] = {-1, -1};
Q.push(R);
coord curr, neigh;
while (!Q.empty())
{
curr = Q.front();
Q.pop();
if (curr == J)
break;
while ((neigh = get_neighbour(curr)) != NO_NEIGH)
if (neigh != NOT_YET && m_dist[neigh.i][neigh.j] == INF_CHAR)
{
m_dist[neigh.i][neigh.j] = m_dist[curr.i][curr.j] + 1;
m_parrent[neigh.i][neigh.j] = curr;
Q.push(neigh);
}
}
}
struct solution
{
coord x;
int d;
};
solution solve()
{
char **m_dist;
coord **m_parrent;
BFS(m_dist, m_parrent);
int d = m_dist[J.i][J.j];
coord curr = J, upper_middle, lower_middle;
while ((d / 2 + 1) != m_dist[curr.i][curr.j])
curr = m_parrent[curr.i][curr.j];
upper_middle = curr; lower_middle = m_parrent[curr.i][curr.j];
if (d % 2 == 0)
return {{lower_middle.i + 1, lower_middle.j + 1}, d / 2 + 1};
while ((curr = get_neighbour(lower_middle)) != NO_NEIGH)
if (curr != NOT_YET && curr != upper_middle && curr.is_neighbour(upper_middle))
break;
if (lower_middle.j < curr.j)
{
coord prev = lower_middle, next = m_parrent[lower_middle.i][lower_middle.j], stop = {-1, -1};
while (next != stop)
{
coord neigh;
while ((neigh = get_neighbour(next)) != NO_NEIGH)
if (neigh != NOT_YET && neigh != prev && neigh.is_neighbour(prev))
{
curr = lower_middle; goto eticheta1;
}
prev = next;
next = m_parrent[next.i][next.j];
}
}
eticheta1:
if (upper_middle.j < curr.j)
{
coord prev = J, next = m_parrent[J.i][J.j];
while (next != lower_middle)
{
coord neigh;
while ((neigh = get_neighbour(next)) != NO_NEIGH)
if (neigh != NOT_YET && neigh != prev && neigh.is_neighbour(prev))
{
curr = upper_middle; goto eticheta2;
}
prev = next;
next = m_parrent[next.i][next.j];
}
}
eticheta2:
for (int i = 0; i < nr_linii; i++)
{
delete [] m_dist[i];
delete [] m_parrent[i];
}
delete [] m_dist;
delete [] m_parrent;
return {{curr.i + 1, curr.j + 1}, d / 2 + 2};
}
int main()
{
citesc_date("rj.in");
solution S = solve();
FILE *f = fopen("rj.out", "w");
fprintf(f, "%d %d %d", S.d, S.x.i, S.x.j);
for (int i = 0; i < nr_linii; i++)
delete [] m_city[i];
delete [] m_city;
fclose(f);
}