Pagini recente » Cod sursa (job #2089073) | Cod sursa (job #785995) | Cod sursa (job #729791) | Cod sursa (job #427425) | Cod sursa (job #2116350)
#include <fstream>
#include <queue>
#define intrare "rj.in"
#define iesire "rj.out"
using namespace std;
ifstream in(intrare);
ofstream out(iesire);
struct p
{
int x, y;
};
p romeo, julieta;
short traseu_romeo[105][105];
short traseu_julieta[105][105];
int n, m;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
queue < pair < int , int > > coada;
bool OK(int i, int j)
{
if(i < 1 || i > n || j < 1 || j > m)
return false;
return true;
}
void Read()
{
in >> n >> m;
in.get();
for(int i = 1; i <= n; i++)
{
char c[105];
in.getline(c, 101);
for(unsigned j = 0; j < m; j++)
if(c[j] == 'R')
romeo = {i, j + 1};
else if(c[j] == 'J')
julieta = {i, j + 1};
else if(c[j] == 'X')
traseu_romeo[i][j+1] = traseu_julieta[i][j+1] = -1;
}
}
void Lee_Romeo()
{
traseu_romeo[romeo.x][romeo.y] = 1;
coada.push(make_pair(romeo.x, romeo.y));
while(!coada.empty())
{
int x = coada.front().first;
int y = coada.front().second;
coada.pop();
for(int d = 0; d < 8; d++)
{
int x_new = x + dx[d];
int y_new = y + dy[d];
if(OK(x_new, y_new) && traseu_romeo[x_new][y_new] == 0)
{
traseu_romeo[x_new][y_new] = traseu_romeo[x][y] + 1;
coada.push(make_pair(x_new, y_new));
}
}
}
}
void Lee_Julieta()
{
traseu_julieta[julieta.x][julieta.y] = 1;
coada.push(make_pair(julieta.x, julieta.y));
while(!coada.empty())
{
int x = coada.front().first;
int y = coada.front().second;
coada.pop();
for(int d = 0; d < 8; d++)
{
int x_new = x + dx[d];
int y_new = y + dy[d];
if(OK(x_new, y_new) && traseu_julieta[x_new][y_new] == 0)
{
traseu_julieta[x_new][y_new] = traseu_julieta[x][y] + 1;
coada.push(make_pair(x_new, y_new));
}
}
}
}
void Caut_Drum()
{
traseu_romeo[romeo.x][romeo.y] = -1;
traseu_julieta[julieta.x][julieta.y] = -1;
int lungime = 10000000;
int x_lungime = 0, y_lungime = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(traseu_romeo[i][j] > 0 && traseu_julieta[i][j] > 0)
if(traseu_romeo[i][j] == traseu_julieta[i][j])
{
if(traseu_romeo[i][j] < lungime)
lungime = traseu_romeo[i][j], x_lungime = i, y_lungime = j;
else if(traseu_romeo[i][j] == lungime)
if(j < y_lungime)
lungime = traseu_romeo[i][j], x_lungime = i, y_lungime = j;
}
}
out << lungime << " " << x_lungime << " " << y_lungime;
}
int main()
{
Read();
Lee_Romeo();
Lee_Julieta();
Caut_Drum();
return 0;
}