#include<fstream>
#include<queue>
using namespace std;
struct position { short row, col, step; };
void read_init(short** &R, short ** &J, short &max_row, short &max_col, position &r_start, position &j_start)
{
ifstream file("rj.in");
char c;
file >> max_row >> max_col;
R = new short*[max_row];
J = new short*[max_row];
for (int i = 0; i < max_row; i++)
{
R[i] = new short[max_col];
J[i] = new short[max_col];
for (int j = 0; j < max_col; j++)
{
do
{
c = file.get();
} while (c == '\n');
if (c == 'X')
R[i][j] = J[i][j] = -1;
else
if (c == ' ')
R[i][j] = J[i][j] = 0;
else
if (c == 'R')
{
R[i][j] = J[i][j] = -1;
r_start.row = i;
r_start.col = j;
r_start.step = 1;
}
else
if (c == 'J')
{
R[i][j] = J[i][j] = -1;
j_start.row = i;
j_start.col = j;
j_start.step = 1;
}
}
}
file.close();
}
void meeting_point(short **R, short **J, short max_row, short max_col, position r_pos, position j_pos)
{
ofstream g("rj.out");
bool found = false;
queue<position> r_q, j_q;
r_q.push(r_pos);
j_q.push(j_pos);
while (!found)
{
do
{
r_pos = r_q.front();
r_q.pop();
if (r_pos.row - 1 >= 0)
{
if (r_pos.col - 1 >= 0 && !R[r_pos.row - 1][r_pos.col - 1])
{
R[r_pos.row - 1][r_pos.col - 1] = r_pos.step + 1;
r_q.push({ r_pos.row - 1, r_pos.col - 1, r_pos.step + 1 });
}
if (!R[r_pos.row - 1][r_pos.col])
{
R[r_pos.row - 1][r_pos.col] = r_pos.step + 1;
r_q.push({ r_pos.row - 1, r_pos.col, r_pos.step + 1 });
}
if (r_pos.col + 1 < max_col && !R[r_pos.row - 1][r_pos.col + 1])
{
R[r_pos.row - 1][r_pos.col + 1] = r_pos.step + 1;
r_q.push({ r_pos.row - 1, r_pos.col + 1, r_pos.step + 1 });
}
}
if (r_pos.col - 1 >= 0 && !R[r_pos.row][r_pos.col - 1])
{
R[r_pos.row][r_pos.col - 1] = r_pos.step + 1;
r_q.push({ r_pos.row, r_pos.col - 1, r_pos.step + 1 });
}
if (r_pos.col + 1 < max_col && !R[r_pos.row][r_pos.col + 1])
{
R[r_pos.row][r_pos.col + 1] = r_pos.step + 1;
r_q.push({ r_pos.row, r_pos.col + 1, r_pos.step + 1 });
}
if (r_pos.row + 1 < max_row)
{
if (r_pos.col - 1 >= 0 && !R[r_pos.row + 1][r_pos.col - 1])
{
R[r_pos.row + 1][r_pos.col - 1] = r_pos.step + 1;
r_q.push({ r_pos.row + 1, r_pos.col - 1, r_pos.step + 1 });
}
if (!R[r_pos.row + 1][r_pos.col])
{
R[r_pos.row + 1][r_pos.col] = r_pos.step + 1;
r_q.push({ r_pos.row + 1, r_pos.col, r_pos.step + 1 });
}
if (r_pos.col + 1 < max_col && !R[r_pos.row + 1][r_pos.col + 1])
{
R[r_pos.row + 1][r_pos.col + 1] = r_pos.step + 1;
r_q.push({ r_pos.row + 1, r_pos.col + 1, r_pos.step + 1 });
}
}
} while (!r_q.empty() && r_q.front().step == r_pos.step);
do
{
j_pos = j_q.front();
j_q.pop();
if (j_pos.row - 1 >= 0)
{
if (j_pos.col - 1 >= 0 && !J[j_pos.row - 1][j_pos.col - 1])
{
J[j_pos.row - 1][j_pos.col - 1] = j_pos.step + 1;
if (J[j_pos.row - 1][j_pos.col - 1] == R[j_pos.row - 1][j_pos.col - 1])
{
found = true;
g << j_pos.step + 1 << ' ' << j_pos.row << ' ' << j_pos.col;
break;
}
j_q.push({ j_pos.row - 1, j_pos.col - 1, j_pos.step + 1 });
}
if (!J[j_pos.row - 1][j_pos.col])
{
J[j_pos.row - 1][j_pos.col] = j_pos.step + 1;
if (J[j_pos.row - 1][j_pos.col] == R[j_pos.row - 1][j_pos.col])
{
found = true;
g << j_pos.step + 1 << ' ' << j_pos.row << ' ' << j_pos.col + 1;
break;
}
j_q.push({ j_pos.row - 1, j_pos.col, j_pos.step + 1 });
}
if (j_pos.col + 1 < max_col && !J[j_pos.row - 1][j_pos.col + 1])
{
J[j_pos.row - 1][j_pos.col + 1] = j_pos.step + 1;
if (J[j_pos.row - 1][j_pos.col + 1] == R[j_pos.row - 1][j_pos.col + 1])
{
found = true;
g << j_pos.step + 1 << ' ' << j_pos.row << ' ' << j_pos.col + 2;
break;
}
j_q.push({ j_pos.row - 1, j_pos.col + 1, j_pos.step + 1 });
}
}
if (j_pos.col - 1 >= 0 && !J[j_pos.row][j_pos.col - 1])
{
J[j_pos.row][j_pos.col - 1] = j_pos.step + 1;
if (J[j_pos.row][j_pos.col - 1] == R[j_pos.row][j_pos.col - 1])
{
found = true;
g << j_pos.step + 1 << ' ' << j_pos.row + 1 << ' ' << j_pos.col;
break;
}
j_q.push({ j_pos.row, j_pos.col - 1, j_pos.step + 1 });
}
if (j_pos.col + 1 < max_col && !J[j_pos.row][j_pos.col + 1])
{
J[j_pos.row][j_pos.col + 1] = j_pos.step + 1;
if (J[j_pos.row][j_pos.col + 1] == R[j_pos.row][j_pos.col + 1])
{
found = true;
g << j_pos.step + 1 << ' ' << j_pos.row + 1 << ' ' << j_pos.col + 2;
break;
}
j_q.push({ j_pos.row, j_pos.col + 1, j_pos.step + 1 });
}
if (j_pos.row + 1 < max_row)
{
if (j_pos.col - 1 >= 0 && !J[j_pos.row + 1][j_pos.col - 1])
{
J[j_pos.row + 1][j_pos.col - 1] = j_pos.step + 1;
if (J[j_pos.row + 1][j_pos.col - 1] == R[j_pos.row + 1][j_pos.col - 1])
{
found = true;
g << j_pos.step + 1 << ' ' << j_pos.row + 2 << ' ' << j_pos.col;
break;
}
j_q.push({ j_pos.row + 1, j_pos.col - 1, j_pos.step + 1 });
}
if (!J[j_pos.row + 1][j_pos.col])
{
J[j_pos.row + 1][j_pos.col] = j_pos.step + 1;
if (J[j_pos.row + 1][j_pos.col] == R[j_pos.row + 1][j_pos.col])
{
found = true;
g << j_pos.step + 1 << ' ' << j_pos.row + 2 << ' ' << j_pos.col + 1;
break;
}
j_q.push({ j_pos.row + 1, j_pos.col, j_pos.step + 1 });
}
if (j_pos.col + 1 < max_col && !J[j_pos.row + 1][j_pos.col + 1])
{
J[j_pos.row + 1][j_pos.col + 1] = j_pos.step + 1;
if (J[j_pos.row + 1][j_pos.col + 1] == R[j_pos.row + 1][j_pos.col + 1])
{
found = true;
g << j_pos.step + 1 << ' ' << j_pos.row + 2 << ' ' << j_pos.col + 2;
break;
}
j_q.push({ j_pos.row + 1, j_pos.col + 1, j_pos.step + 1 });
}
}
} while (!j_q.empty() && j_q.front().step == j_pos.step);
}
g.close();
}
void clean(short** &R, short ** &J, short &max_row, short &max_col)
{
for (int i = 0; i < max_row; i++)
{
delete[] R[i];
delete[] J[i];
}
delete[] R;
delete[] J;
R = NULL;
J = NULL;
max_row = max_col = 0;
}
int main()
{
short **R, **J, max_row, max_col;
position r_start, j_start;
read_init(R, J, max_row, max_col, r_start, j_start);
meeting_point(R, J, max_row, max_col, r_start, j_start);
clean(R, J, max_row, max_col);
return 0;
}