Pagini recente » Cod sursa (job #142150) | Autentificare | Cod sursa (job #2024090) | Cod sursa (job #2981353) | Cod sursa (job #1894927)
#include <fstream>
#include <string>
#include <deque>
#define DEF 101
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
struct coada {
unsigned short x;
unsigned short y;
unsigned short p;
};
unsigned short R_i, R_j, J_i, J_j, n, m, A[DEF][DEF], F[DEF][DEF], sol = DEF*DEF, sol_i, sol_j;
deque <coada> c;
short di[] = {-1, -1, -1, 0, 1, 1, 1, 0},
dj[] = {-1, 0, 1, 1, 1, 0, -1, -1};
coada cons (unsigned short x, unsigned y, unsigned p) {
coada temp;
temp.x = x;
temp.y = y;
temp.p = p;
return temp;
}
int main () {
fin >> n >> m;
char read[DEF];
for (int i = 1; i <= n; i++) {
fin.get ();
fin.get (read + 1, DEF);
for (int j = 1; j <= m; j++) {
if (read[j] == 'X')
A[i][j] = DEF*DEF;
if (read[j] == 'R') {
R_i = i;
R_j = j;
}
if (read[j] == 'J') {
J_i = i;
J_j = j;
}
}
}
c.push_back (cons (R_i, R_j, 0));
F[R_i][R_j] = DEF*DEF + 1;
while (!c.empty()) {
short i = c.front ().x;
short j = c.front ().y;
short p = c.front ().p;
for (int d = 0; d < 8; d++) {
short new_i = i + di[d];
short new_j = j + dj[d];
if (F[new_i][new_j] == 0 && new_i >= 1 && new_i <= n && new_j >= 1 && new_j <= m && A[new_i][new_j] != DEF*DEF) {
F[new_i][new_j] = p + 1;
c.push_back (cons (new_i, new_j, p + 1));
}
}
c.pop_front ();
}
c.erase (c.begin (), c.end ());
c.push_back (cons (J_i, J_j, 0));
A[J_i][J_j] = DEF*DEF + 1;
while (!c.empty ()) {
short i = c.front ().x;
short j = c.front ().y;
short p = c.front ().p;
for (int d = 0; d < 8; d++) {
short new_i = i + di[d];
short new_j = j + dj[d];
if (A[new_i][new_j] == 0 && new_i >= 1 && new_i <= n && new_j >= 1 && new_j <= m) {
A[new_i][new_j] = p + 1;
c.push_back (cons (new_i, new_j, p + 1));
if (A[new_i][new_j] == F[new_i][new_j] && A[new_i][new_j] == sol && new_j < sol_j) {
sol_i = i;
sol_j = j;
continue;
}
if (A[new_i][new_j] == F[new_i][new_j] && A[new_i][new_j] < sol) {
sol = A[new_i][new_j];
sol_i = new_i;
sol_j = new_j;
}
}
}
c.pop_front ();
}
fout << sol + 1 << " " << sol_i << " " << sol_j << "\n";
return 0;
}