Pagini recente » Cod sursa (job #1632768) | Cod sursa (job #50768) | Cod sursa (job #2573192) | Cod sursa (job #3261858) | Cod sursa (job #2981435)
#include <fstream>
#include <queue>
using namespace std;
ifstream f ("rj.in");
ofstream g ("rj.out");
const int max_size = 101, max_dir = 8;
char a[max_size][max_size];
int r[max_size][max_size], jl[max_size][max_size], n, m,
di[] = {-1, -1, 0, 1, 1, 1, 0, -1},
dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
queue <pair <int,int>> coada;
void lee1 (int is, int js)
{
r[is][js] = 1;
coada.push(make_pair(is, js));
while (!coada.empty())
{
int i = coada.front().first, j = coada.front().second;
for (int k = 0; k < max_dir; k++)
{
int iv = i + di[k], jv = j + dj[k];
if (iv >= 0 && jv >= 0 && iv < n && jv < m && (r[iv][jv] == 0 || r[i][j] + 1 < r[iv][jv]))
{
r[iv][jv] = r[i][j] + 1;
coada.push(make_pair(iv, jv));
}
}
coada.pop();
}
}
void lee2 (int is, int js)
{
jl[is][js] = 1;
coada.push(make_pair(is, js));
while (!coada.empty())
{
int i = coada.front().first, j = coada.front().second;
for (int k = 0; k < max_dir; k++)
{
int iv = i + di[k], jv = j + dj[k];
if (iv >= 0 && jv >= 0 && iv < n && jv < m && (jl[iv][jv] == 0 || jl[i][j] + 1 < jl[iv][jv]))
{
jl[iv][jv] = jl[i][j] + 1;
coada.push(make_pair(iv, jv));
}
}
coada.pop();
}
}
int main ()
{
f >> n >> m;
f.get();
int ir, jr, ij, jj;
for (int i = 0; i < n; i++)
{
f.getline(a[i], max_size + 1);
for (int j = 0; j < m; j++)
{
if (a[i][j] == ' ')
{
r[i][j] = 0;
jl[i][j] = 0;
}
if (a[i][j] == 'X')
{
r[i][j] = -1;
jl[i][j] = -1;
}
if (a[i][j] == 'R')
{
r[i][j] = 0;
jl[i][j] = 0;
ir = i;
jr = j;
}
if (a[i][j] == 'J')
{
r[i][j] = 0;
jl[i][j] = 0;
ij = i;
jj = j;
}
}
}
lee1(ir, jr);
lee2(ij, jj);
int irez, jrez, rez = 1e9 + 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (r[i][j] != -1 && r[i][j] != 0 && r[i][j] == jl[i][j])
{
if (r[i][j] < rez)
{
rez = r[i][j];
irez = i;
jrez = j;
}
}
}
}
g << rez << " " << irez + 1 << " " << jrez + 1;
return 0;
}