Pagini recente » Cod sursa (job #2392030) | Cod sursa (job #1346373) | Cod sursa (job #2889836) | Cod sursa (job #33325) | Cod sursa (job #3192863)
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int dx[]={-1,-1,-1,0,1,1,1,0};
int dy[]={-1,0,1,1,1,0,-1,-1};
int n, m, Tmin = 1e9, costR[105][105], costJ[105][105], imin, jmin, Ri, Rj, Ji, Jj;
queue <pair <int, int> > q;
char ch[105];
bool inMat(int i, int j)
{
return i >= 1 && i <= n && j >= 1 && j <= m;
}
void lee()
{
q.push({Ri, Rj});
while (!q.empty()) {
int i = q.front().first;
int j = q.front().second;
q.pop();
for (int k = 0; k < 8; ++k) {
int iv = i + dx[k];
int jv = j + dy[k];
if (inMat(iv, jv) && costR[iv][jv] == 0) {
costR[iv][jv] = costR[i][j] + 1;
q.push({iv, jv});
}
}
}
q.push({Ji, Jj});
while (!q.empty()) {
int i = q.front().first;
int j = q.front().second;
q.pop();
for (int k = 0; k < 8; ++k) {
int iv = i + dx[k];
int jv = j + dy[k];
if (inMat(iv, jv) && costJ[iv][jv] == 0) {
costJ[iv][jv] = costJ[i][j] + 1;
q.push({iv, jv});
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if ((costJ[i][j] == costR[i][j]) && costJ[i][j] < Tmin && costJ[i][j] > 1) {
Tmin = costJ[i][j];
imin = i;
jmin = j;
}
}
}
g << Tmin << ' ' << imin << ' ' << jmin;
}
int main()
{
f >> n >> m;
f.get();
for (int i = 1; i <= n; ++i) {
f.getline(ch, 105);
for (int j = 1; j <= m; ++j) {
if (ch[j - 1] == 'X') {
costJ[i][j] = costR[i][j] = 1;
}
else if (ch[j - 1] == 'R') {
Ri = i;
Rj = j;
costR[i][j] = 1;
costJ[i][j] = 1;
}
else if (ch[j - 1] == 'J') {
Ji = i;
Jj = j;
costJ[i][j] = 1;
costR[i][j] = 1;
}
}
}
lee();
return 0;
}