#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
void AfiseazaLista(vector<list<int> > L, int n)
{
int i;
cout << "\n";
for (i = 0; i < n; i++)
{
cout << i << ": ";
for (list<int>::iterator k = L[i].begin(); k != L[i].end(); k++)
cout << *k << " ";
cout << "\n";
}
}
/* 0 - 1 - 2 - 3
| | | |
4 - 5 - 6 - 7 <-- un graf asociat unei matrice
| | | |
8 - 9 - 10- 11
*/
vector<list<pair<int,char> > > CreeazaListaAdiacenta(char** a, int n, int m)
{
vector<list<pair<int,char> > > L(n * m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// ma aflu pe nodul i * m + j
int nord = (i - 1) * m + j;
int sud = (i + 1) * m + j;
int est = i * m + j + 1;
int vest = i * m + j - 1;
int NV = (i - 1) * m + j - 1;
int NE = (i - 1) * m + j + 1;
int SV = (i + 1) * m + j - 1;
int SE = (i + 1) * m + j + 1;
if (NV >= 0 && NV % m != m - 1)
L[i * m + j].push_back( make_pair(NV, a[i - 1][j - 1]) );
if (nord >= 0)
L[i * m + j].push_back( make_pair(nord, a[i - 1][j]) );
if (NE >= 0 && NE % m != 0)
L[i * m + j].push_back( make_pair(NE, a[i - 1][j + 1]) );
if (vest >= 0 && vest % m != m - 1)
L[i * m + j].push_back( make_pair(vest, a[i][j - 1]) );
if (est <= n * m && est % m != 0)
L[i * m + j].push_back( make_pair(est, a[i][j + 1]) );
if (SV < n * m && SV % m != m - 1)
L[i * m + j].push_back( make_pair(SV, a[i + 1][j - 1]) );
if (sud < n * m)
L[i * m + j].push_back( make_pair(sud, a[i + 1][j]) );
if (SE < n * m && SE % m != 0)
L[i * m + j].push_back( make_pair(SE, a[i + 1][j + 1]) );
}
}
return L;
}
bool EsteCaracterAcceptabil(char x)
{
return x == ' ' || x == 'R' || x == 'J';
}
vector<list<int> > CreeazaListaAdiacentaRedusa(char** a, int n, int m, int &rom, int &jul)
{
vector<list<int> > L(n * m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (a[i][j] == ' ' || a[i][j] == 'R' || a[i][j] == 'J')
{
// ma aflu pe nodul cu nr i * m + j
if (a[i][j] == 'R')
rom = i * m + j;
if (a[i][j] == 'J')
jul = i * m + j;
int nord = (i - 1) * m + j;
int sud = (i + 1) * m + j;
int est = i * m + j + 1;
int vest = i * m + j - 1;
int NV = (i - 1) * m + j - 1;
int NE = (i - 1) * m + j + 1;
int SV = (i + 1) * m + j - 1;
int SE = (i + 1) * m + j + 1;
if (NV >= 0 && NV % m != m - 1 && EsteCaracterAcceptabil(a[i - 1][j - 1]) )
L[i * m + j].push_back(NV);
if (nord >= 0 && EsteCaracterAcceptabil(a[i - 1][j]) )
L[i * m + j].push_back(nord);
if (NE >= 0 && NE % m != 0 && EsteCaracterAcceptabil(a[i - 1][j + 1]) )
L[i * m + j].push_back(NE);
if (vest >= 0 && vest % m != m - 1 && EsteCaracterAcceptabil(a[i][j - 1]) )
L[i * m + j].push_back(vest);
if (est <= n * m && est % m != 0 && EsteCaracterAcceptabil(a[i][j + 1]) )
L[i * m + j].push_back(est);
if (SV < n * m && SV % m != m - 1 && EsteCaracterAcceptabil(a[i + 1][j - 1]) )
L[i * m + j].push_back(SV);
if (sud < n * m && EsteCaracterAcceptabil(a[i + 1][j]) )
L[i * m + j].push_back(sud);
if (SE < n * m && SE % m != 0 && EsteCaracterAcceptabil(a[i + 1][j + 1]) )
L[i * m + j].push_back(SE);
}
return L;
}
void ParcurgeGraf(vector<list<int> > L, int n, int m, int romeo, int julieta, int &timp, int &intalnire)
{
vector<pair<bool, char> > viz(n * m, make_pair(false, '-'));
queue<int> C1, C2;
int i, exploreazaR = 1, exploreazaJ = 1, aux;
timp = 1;
C1.push(romeo);
viz[romeo] = make_pair(true, 'R');
C2.push(julieta);
viz[julieta] = make_pair(true, 'J');
intalnire = -1;
while (!C1.empty() && !C2.empty() && intalnire == -1)
{
timp++;
aux = exploreazaR;
exploreazaR = 0;
for (int k = 0; k < aux; k++)
{
i = C1.front();
C1.pop();
for (list<int>::iterator j = L[i].begin(); j != L[i].end(); j++)
if (!viz[*j].first)
{
viz[*j].first = true;
viz[*j].second = 'R';
C1.push(*j);
exploreazaR++;
}
}
aux = exploreazaJ;
exploreazaJ = 0;
for (int k = 0; k < aux; k++)
{
i = C2.front();
C2.pop();
for (list<int>::iterator j = L[i].begin(); j != L[i].end(); j++)
if (!viz[*j].first)
{
viz[*j].first = true;
viz[*j].second = 'J';
C2.push(*j);
exploreazaJ++;
}
else if (viz[*j].second == 'R')
{
intalnire = *j;
break;
}
}
}
}
int main()
{
ifstream f("rj.in");
ofstream g("rj.out");
vector<list<int> > L;
char** a, c;
int n, m, i, j, romeo, julieta, timp, locIntalnire;
f >> n >> m;
a = new char*[n];
for (i = 0; i < n; i++)
a[i] = new char[m];
for (i = 0; i < n; i++)
{
f.get(c);
for (j = 0; j < m; j++)
f.get(a[i][j]);
}
L = CreeazaListaAdiacentaRedusa(a, n, m, romeo, julieta);
//cout << romeo << "&" << julieta;
//AfiseazaLista(L, n * m);
ParcurgeGraf(L, n, m, romeo, julieta, timp, locIntalnire);
//cout << "Timp: " << timp << "\nLoc intalnire: " << locIntalnire / m + 1 << ", " << locIntalnire % m + 1 << "\n";
g << timp << " " << locIntalnire / m + 1 << " " << locIntalnire % m + 1;
return 0;
}