Pagini recente » Cod sursa (job #1871733) | Cod sursa (job #1703774) | Cod sursa (job #2056362) | Cod sursa (job #741942) | Cod sursa (job #2270172)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct Coord {
int i, j;
};
queue <Coord> Q;
int N, M, matrix_R[110][110], matrix_J[110][110], t_min;
Coord R, J, meeting_point;
int di[8] = {-1, 0, 1, 0,-1,-1, 1, 1};
int dj[8] = {0, 1, 0, -1,-1, 1, 1,-1};
void Copy_Matrix()
{
for (int i = 0; i < N+1; ++i)
for (int j = 0; j < M+1; ++j)
matrix_J[i][j] = matrix_R[i][j];
}
void Border()
{
for (int j = 0; j <= M+1; ++j){
matrix_R[0][j] = -1;
matrix_R[N+1][j] = -1;
matrix_J[0][j] = -1;
matrix_J[N+1][j] = -1;
}
for (int i = 1; i <= N; ++i){
matrix_R[i][0] = -1;
matrix_R[i][M+1] = -1;
matrix_J[i][0] = -1;
matrix_J[i][M+1] = -1;
}
}
void Solve()
{
Q.push(J);
matrix_J[J.i][J.j] = 1;
/// Julieta
while (!Q.empty()){
Coord nod = Q.front();
Q.pop();
for (int d = 0; d < 8; ++d){
Coord elem;
int ci, cj;
ci = nod.i + di[d];
cj = nod.j + dj[d];
if (matrix_J[ci][cj] == 0){
matrix_J[ci][cj] = 1 + matrix_J[nod.i][nod.j];
elem.i = ci;
elem.j = cj;
Q.push(elem);
}
}
}
Q.push(R);
matrix_R[R.i][R.j] = 1;
/// Romeo
while (!Q.empty()){
Coord nod = Q.front();
Q.pop();
for (int d = 0; d < 8; ++d){
Coord elem;
int ci, cj;
ci = nod.i + di[d];
cj = nod.j + dj[d];
if (matrix_R[ci][cj] == 0){
matrix_R[ci][cj] = 1 + matrix_R[nod.i][nod.j];
elem.i = ci;
elem.j = cj;
Q.push(elem);
}
}
}
}
void Read()
{
char cr;
bool newline = false;
fin >> N >> M;
t_min = INT_MAX;
Border();
for (int i = 1; i <= N; ++i){
if (!newline)
fin.get(cr);
else
newline = false;
for (int j = 1; j <= M; ++j){
fin.get(cr);
if (cr != '\n'){
switch (cr){
case 'X':
matrix_R[i][j] = -1;
break;
case ' ':
matrix_R[i][j] = 0;
break;
case 'R':
R.i = i;
R.j = j;
break;
case 'J':
J.i = i;
J.j = j;
break;
}
}
else{
newline = true;
break;
}
}
}
Copy_Matrix();
}
void Write()
{
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
if (matrix_R[i][j] == matrix_J[i][j] && matrix_R[i][j] != -1 && t_min > matrix_R[i][j]){
t_min = matrix_R[i][j];
meeting_point.i = i;
meeting_point.j = j;
}
fout << t_min << " " << meeting_point.i << " " << meeting_point.j;
}
int main()
{
Read();
Solve();
Write();
return 0;
}