Pagini recente » Cod sursa (job #2378397) | Cod sursa (job #1294603) | Cod sursa (job #2851690) | Cod sursa (job #229705) | Cod sursa (job #2841357)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n;
int m;
int ma_r[105][105]; // matricea pentru drumul lui Romeo
int ma_j[105][105]; // matricea pentru drumul Julietei
int xrstart, yrstart; // poz de inceput a lui Romeo
int xjstart, yjstart; // poz de inceput a Julietei
const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
queue<pair<int, int>> R; // coada pt algoritm lee Romeo
queue<pair<int, int>> J; // coada pt algoritm lee Julieta
bool prima_sol = true;
bool is_inside(int x, int y)
{
return (1 <= x && x <= n && 1 <= y && y <= m);
}
void lee_romeo(int istart, int jstart)
{
ma_r[istart][jstart] = 1;
R.push(make_pair(istart, jstart));
while (!R.empty())
{
int icurent, jcurent;
icurent = R.front().first;
jcurent = R.front().second;
R.pop();
for (int d = 0; d < 8; d++)
{
int inou, jnou;
inou = icurent + dx[d];
jnou = jcurent + dy[d];
if (is_inside(inou, jnou) && ma_r[inou][jnou] == 0)
{
ma_r[inou][jnou] = ma_r[icurent][jcurent] + 1;
R.push(make_pair(inou, jnou));
}
}
}
}
void lee_julieta(int istart, int jstart)
{
ma_j[istart][jstart] = 1;
J.push(make_pair(istart, jstart));
while (!J.empty())
{
int icurent, jcurent;
icurent = J.front().first;
jcurent = J.front().second;
J.pop();
for (int d = 0; d < 8; d++)
{
int inou, jnou;
inou = icurent + dx[d];
jnou = jcurent + dy[d];
if (is_inside(inou, jnou) && ma_j[inou][jnou] == 0)
{
ma_j[inou][jnou] = ma_j[icurent][jcurent] + 1;
J.push(make_pair(inou, jnou));
}
}
}
}
int main()
{
fin >> n >> m;
fin.get();
for (int i = 1; i <= n; i++)
{
char a;
for (int j = 1; j <= m; j++)
{
a = fin.get();
if (a == 'R')
{
xrstart = i;
yrstart = j;
}
else if (a == 'J')
{
xjstart = i;
yjstart = j;
}
else if (a == 'X')
{
ma_j[i][j] = -1;
ma_r[i][j] = -1;
}
else
{
ma_j[i][j] = 0;
ma_r[i][j] = 0;
}
}
fin.get();
}
lee_romeo(xrstart, yrstart);
lee_julieta(xjstart, yjstart);
int irez = 0;
int jrez = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if(ma_j[i][j] > 0 && ma_r[i][j] >= 0 && ma_j[i][j] == ma_r[i][j])
{
if(prima_sol)
{
irez = i;
jrez = j;
prima_sol = false;
}
else
{
if(ma_j[i][j] < ma_j[irez][jrez])
{
irez = i;
jrez = j;
}
}
}
}
}
fout << ma_j[irez][jrez] << ' ' << irez << ' ' << jrez;
return 0;
}