Pagini recente » Cod sursa (job #2968276) | Cod sursa (job #2470161) | Cod sursa (job #1542650) | Cod sursa (job #369073) | Cod sursa (job #2814863)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");
#define INF 1e9
int n,m;
int rmat[101][101], jmat[101][101];
int dl[] = {0,0,1,-1,1,-1,1,-1};
int dc[] = {1,-1,0,0,-1,1,1,-1};
int validr (int x, int y) {
if (x<1 || y<1 || x>n || y>m)
return 0;
return 1;
}
int validj (int x, int y) {
if (x<1 || y<1 || x>n || y>m)
return 0;
return 1;
}
void leer (int xstart, int ystart) {
deque < pair<int,int> > q;
q.emplace_back(make_pair(xstart, ystart));
while (!q.empty()) {
pair <int,int> key = q.front();
q.pop_front();
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 (!validr(ii,jj) || (rmat[ii][jj] != 0 && rmat[ii][jj] <= rmat[i][j] ))
continue;
rmat[ii][jj] = rmat[i][j] + 1;
q.emplace_back(ii,jj);
}
}
}
void leej (int xstart, int ystart) {
deque < pair<int,int> > q;
q.emplace_back(make_pair(xstart, ystart));
while (!q.empty()) {
pair <int,int> key = q.front();
q.pop_front();
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 (!validj(ii,jj) || (jmat[ii][jj] != 0 && jmat[ii][jj] <= jmat[i][j] ))
continue;
jmat[ii][jj] = jmat[i][j] + 1;
q.emplace_back(ii,jj);
}
}
}
int main () {
in >> n >> m;
in.get();
int rx,ry,jx,jy;
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;
}
}
}
leer(rx,ry);
leej(jx, jy);
int x,y, best = INF;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (rmat[i][j] == jmat[i][j] && rmat[i][j] < INF && rmat[i][j]>0) {
x = i;
y = j;
best = rmat[i][j];
}
}
}
out << best << ' ' << x << ' ' << y << '\n';
return 0;
}