Pagini recente » Cod sursa (job #1290185) | Cod sursa (job #2320328) | Cod sursa (job #1381669) | Cod sursa (job #1551779) | Cod sursa (job #2572892)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
queue <pair <int,int> > coada;
int iR, jR, iF, jF;
char A[101][101];
int mt[101][101], R[101][101], J[101][101], linii, coloane;
const int di[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dj[] = {-1, 0, 1, 1, 1, 0, -1, -1};
bool vizitat[101][101];
bool OK(int i, int j) {
if (i < 1 || j < 1 || i > linii || j > coloane) {
return false;
}
if (mt[i][j] == -1) {
return false;
}
return true;
}
void Lee1 (int startx, int starty) {
coada.push(make_pair(startx, starty));
vizitat[startx][starty] = true;
while (!coada.empty()) {
int i = coada.front().first, j = coada.front().second;
coada.pop();
for (int k = 0; k < 8; k++) {
int i_urmator = i + di[k], j_urmator = j + dj[k];
if (OK(i_urmator, j_urmator)) {
if (!vizitat[i_urmator][j_urmator] && R[i_urmator][j_urmator] == 0) {
coada.push(make_pair(i_urmator, j_urmator));
vizitat[i_urmator][j_urmator] = true;
R[i_urmator][j_urmator] = R[i][j] + 1;
}
}
}
}
}
void Lee2 (int startx, int starty) {
coada.push(make_pair(startx, starty));
vizitat[startx][starty] = true;
while (!coada.empty()) {
int i = coada.front().first, j = coada.front().second;
coada.pop();
for (int k = 0; k < 8; k++) {
int i_urmator = i + di[k], j_urmator = j + dj[k];
if (OK(i_urmator, j_urmator)) {
if (!vizitat[i_urmator][j_urmator] && J[i_urmator][j_urmator] == 0) {
coada.push(make_pair(i_urmator, j_urmator));
vizitat[i_urmator][j_urmator] = true;
J[i_urmator][j_urmator] = J[i][j] + 1;
}
}
}
}
}
int main() {
fin >> linii >> coloane;
fin.get();
for (int i = 1; i <= linii; i++) {
fin.getline(A[i], 101);
}
for (int i = 1; i <= linii; i++) {
for (int j = 0; j < coloane; j++) {
if (A[i][j] == ' ') {
mt[i][j + 1] = 0;
}
else if (A[i][j] == 'X') {
mt[i][j + 1] = -1;
}
else if (A[i][j] == 'R') {
mt[i][j + 1] = 0;
iR = i;
jR = j + 1;
}
else if (A[i][j] == 'J') {
mt[i][j + 1] = 0;
iF = i;
jF = j + 1;
}
}
}
Lee1(iR,jR);
for (int i = 1; i <= linii; i++) {
for (int j = 1; j <= coloane; j++) {
vizitat[i][j] = false;
}
}
Lee2(iF,jF);
int minim = 10000000000, lr = 0, cr = 0;
for (int i = 1; i <= linii; i++) {
for (int j = 1; j <= coloane; j++) {
if (R[i][j] == J[i][j] && R[i][j] != 0) {
int rez = R[i][j];
if (rez < minim) {
minim = rez;
lr = i;
cr = j;
}
else if (rez == minim) {
if (i < lr) {
lr = i;
cr = j;
}
else if (i == lr) {
lr = i;
cr = j;
}
}
}
}
}
// for (int i = 1; i <= linii; i++) {
// for (int j = 1; j <= coloane; j++) {
// fout << R[i][j] << ' ';
// }
// fout << '\n';
// }
// fout << '\n';
// for (int i = 1; i <= linii; i++) {
// for (int j = 1; j <= coloane; j++) {
// fout << J[i][j] << ' ';
// }
// fout << '\n';
// }
fout << minim + 1 << ' ' << lr << ' ' << cr;
return 0;
}