Pagini recente » Cod sursa (job #2616951) | Cod sursa (job #1785431) | Cod sursa (job #2542579) | Cod sursa (job #314923) | Cod sursa (job #3208812)
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int n, m;
int rx, ry, jx, jy;
char h[102][102];
unsigned short rm[102][102];
unsigned short jm[102][102];
const unsigned short INF = 20000;
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, -1, 0, 1, -1, 0, 1};
void citire()
{
in >> n >> m;
in.getline(h[0]+1,m+1);
for(int i = 1; i <= n; ++i)
{
in.getline(h[i]+1,m+1);
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(h[i][j] == 'R')
{
rx = i;
ry = j;
}
else if(h[i][j] == 'J')
{
jx = i;
jy = j;
}
}
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
rm[i][j] = INF;
jm[i][j] = INF;
}
}
void romeo()
{
queue<pair<short, short> > q;
q.push(make_pair(rx, ry));
rm[rx][ry] = 0;
while(q.empty() == false)
{
pair<short, short> p = q.front();
q.pop();
for(int k = 0; k < 8; ++k)
{
int newx = p.first + dx[k];
int newy = p.second + dy[k];
if(h[newx][newy] != 'X' && rm[newx][newy] > rm[p.first][p.second] + 1)
{
rm[newx][newy] = rm[p.first][p.second] + 1;
q.push(make_pair(newx, newy));
}
}
}
}
void julieta()
{
queue<pair<short, short> > q;
q.push(make_pair(jx, jy));
jm[jx][jy] = 0;
while(q.empty() == false)
{
pair<short, short> p = q.front();
q.pop();
for(int k = 0; k < 8; ++k)
{
int newx = p.first + dx[k];
int newy = p.second + dy[k];
if(h[newx][newy] != 'X' && jm[newx][newy] > jm[p.first][p.second] + 1)
{
jm[newx][newy] = jm[p.first][p.second] + 1;
q.push(make_pair(newx, newy));
}
}
}
}
void rezolvare()
{
romeo();
julieta();
}
void afisare()
{
int tmin = INF;
int x, y;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(rm[i][j] == jm[i][j] && rm[i][j] < tmin)
{
tmin = rm[i][j];
x = i;
y = j;
}
}
}
out << tmin+1 << " " << x << " " << y;
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}