Pagini recente » Cod sursa (job #588078) | Cod sursa (job #2520783) | Cod sursa (job #1110686) | Cod sursa (job #264337) | Cod sursa (job #1337821)
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
using namespace std;
const int MAXN = 105;
char m[MAXN][MAXN];
int vizr[MAXN][MAXN], vizj[MAXN][MAXN], N, M;
queue<int> qx, qy;
int diri[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dirj[] = {0, 1, 1, 1, 0, -1, -1, -1};
bool in_matrix(int x, int y) {
if(x > 0 && y > 0 && x <= N && y <= M)
return true;
return false;
}
void BFS(int x, int y, int viz[MAXN][MAXN]) {
qx.push(x);
qy.push(y);
viz[x][y] = 1;
while(!qx.empty()) {
int xc = qx.front();
int yc = qy.front();
qx.pop();
qy.pop();
for(int k = 0; k < 8; ++k) {
if(m[xc + diri[k]][yc + dirj[k]] != 'X' && !viz[xc + diri[k]][yc + dirj[k]] && in_matrix(xc + diri[k], yc + dirj[k])) {
qx.push(xc + diri[k]);
qy.push(yc + dirj[k]);
viz[xc + diri[k]][yc + dirj[k]] = viz[xc][yc] + 1;
}
}
}
}
int main()
{
ifstream cin("rj.in");
ofstream cout("rj.out");
int xr = 0, yr = 0, xj = 0, yj = 0;
string s;
cin >> N >> M;
getline(cin, s);
for(int i = 1; i <= N; ++i) {
getline(cin, s);
for(int j = 0; j < M; ++j) {
m[i][j + 1] = s[j];
if(m[i][j] == 'R') {
xr = i;
yr = j;
}
if(m[i][j] == 'J') {
xj = i;
yj = j;
}
}
}
BFS(xr, yr, vizr);
BFS(xj, yj, vizj);
int tmin = N * M, ansx = 0, ansy = 0;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j) {
if(vizr[i][j] && vizr[i][j] == vizj[i][j] && vizr[i][j] < tmin) {
tmin = vizr[i][j];
ansx = i;
ansy = j;
}
}
cout << tmin << ' ' << ansx << ' ' << ansy << '\n';
return 0;
}