Pagini recente » Cod sursa (job #576750) | Cod sursa (job #2293048) | Cod sursa (job #201204) | Cod sursa (job #778090) | Cod sursa (job #2814879)
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");
#define INF 1e9
int n,m,rx,ry,jx,jy;
int rmat[101][101], jmat[101][101];
const int dl[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1};
queue < pair<int,int> > q;
inline bool valid (int x, int y) {
return x>=1 && y>=1 && x<=n && y<=m;
}
int main () {
in >> n >> m;
in.get();
for (int i = 1; i <= n; ++i) {
string line;
getline(in, line);
for (int j = 1; j <= m; ++j) {
char chr = line[j-1];
if (chr == 'X') {
rmat[i][j] = -1;
jmat[i][j] = -1;
}
else if (chr == ' ') {
rmat[i][j] = 0;
jmat[i][j] = 0;
}
else if (chr == 'J') {
rmat[i][j] = 0;
jmat[i][j] = 1;
jx = i, jy = j;
}
else if (chr == 'R') {
rmat[i][j] = 1;
jmat[i][j] = 0;
rx = i, ry = j;
}
}
}
q.emplace(rx,ry);
while (!q.empty()) {
auto key = q.front();
q.pop();
for (int d = 0; d < 8; d++) {
int ii = key.first + dl[d];
int jj = key.second + dc[d];
if (!valid(ii,jj) || (rmat[ii][jj] != 0 && rmat[ii][jj] <= rmat[key.first][key.second] + 1 ))
continue;
rmat[ii][jj] = rmat[key.first][key.second] + 1;
q.emplace(ii,jj);
}
}
q.emplace(jx, jy);
while (!q.empty()) {
auto key = q.front();
q.pop();
int i = key.first;
int j = key.second;
for (int d = 0; d < 8; d++) {
int ii = i + dl[d];
int jj = j + dc[d];
if (!valid(ii,jj) || (jmat[ii][jj] != 0 && jmat[ii][jj] <= jmat[i][j] +1 ))
continue;
jmat[ii][jj] = jmat[i][j] + 1;
q.emplace(ii,jj);
}
}
int x=-1,y=-1, best = 1e9+7;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (rmat[i][j] == jmat[i][j] && rmat[i][j] < best && rmat[i][j]>0) {
x = i;
y = j;
best = rmat[i][j];
}
}
}
out << best << ' ' << x << ' ' << y << '\n';
return 0;
}