#include <fstream>
#include <sstream>
#define nMax 100
#define mMax 100
#define DEBUG 0
#define DB if(DEBUG)
#define toupper1(c) ((c>='a' && c<'z')?c-'a'+'A':c)
using namespace std;
int N,M,dcrt=0,vmax=nMax*mMax+1;
int X=vmax+'X',R=vmax+'R',J=vmax+'J', Spatiu=vmax+' ';
int oras[nMax+1][mMax+1] {Spatiu};
int iR, jR, iJ, jJ, iIntalnire=X, jIntalnire=X, tminDrum;
int di[]={1,0,-1,-1,-1,0,1,1};
int dj[]={-1,-1,-1,0,1,1,1,0};
void citiremat(char numefis[])
{
int i,j,k=0, jcmin, lngLinie;
char cc;
string linie;
ifstream in(numefis);
getline(in,linie);
stringstream ssin(linie);
ssin>>N>>M;
DB printf("N=%d M=%d\n",N,M);
for(i=1;i<=N;i++){
for(j=1;j<=M;j++)
oras[i][j]=Spatiu;
getline(in,linie);
lngLinie = linie.length();
jcmin = M<=lngLinie ? M:lngLinie;
for(j=1;j<=jcmin;j++)
{
cc=linie[j-1];
if(cc==0 || cc=='\r' || cc=='\n') break;
if(cc==EOF) goto Final;
DB k++;
DB printf("%c",cc==' '?'.':cc);
cc=toupper1(cc);
if(cc=='X'||cc=='R'||cc=='J'||cc==' ')
oras[i][j]=vmax+cc;
if(cc=='R') {
iR=i;
jR=j;
}
else if(cc=='J') {
iJ=i;
jJ=j;
}
}
DB printf(" --jcmin=%d\n", jcmin);
linie="";
}
Final: DB printf(" iR=%d jR=%d iJ=%d jJ=%d k=%d ********\n", iR, jR, iJ, jJ, k);
}
void afismat(char * numefis)
{
ofstream out(numefis);
int i,j;
DB printf("\n");
for(i=1;i<=N;i++)
{
out<<endl;
DB printf("\n");
for(j=1;j<=M;j++) {
out<<oras[i][j]<<" ";
DB {
if(oras[i][j]>vmax)
printf(" %c ",oras[i][j]-vmax);
else printf("%2d ",oras[i][j]);
}
}
}
}
int coada[nMax*mMax], kPrim=0,kUltim=0;
void treceInCoada(int i, int j){
coada[kUltim++]=i*(M+1)+j;
}
int extragePrimul(int *j){
int i=coada[kPrim]/(M+1);
*j= coada[kPrim]%(M+1);
kPrim++;
return i;
}
void distante(int oras[][mMax+1], int iStart, int jStart, int iStop, int jStop){
int k, iv, jv, oc, dcrt ;
int iCrt,jCrt;
treceInCoada(iStart, jStart);
oras[iR][jR]=0;
while (kPrim<kUltim) { // coada nu este vida
iCrt = extragePrimul(&jCrt);
if (iCrt == iStop && jCrt == jStop)
break;
dcrt = oras[iCrt][jCrt] + 1;
DB printf("\nicrt=%d jcrt=%d dcrt=%d", iCrt,jCrt,dcrt);
DB afismat("rjinit1.out");
for(k=0;k<8;k++){
iv=iCrt+di[k];
if(iv<1||iv>N) continue;
jv=jCrt+dj[k];
if(jv<1||jv>M) continue;
oc=oras[iv][jv];
if(oc==X || oc==R ) continue;
if(oc > dcrt) { //nevizitat
treceInCoada(iv, jv);
oras[iv][jv]= dcrt;
}
}
}
}
int timpminim(int i, int j){
int k, iv, jv, oc,tmin=X ;
for(k=0;k<8;k++){
iv=i+di[k];
if(iv<1||iv>N) continue;
jv=j+dj[k];
if(jv<1||jv>M) continue;
oc=oras[iv][jv];
if(oc==X) continue;
if(oc%2==0) continue;
if(oc < tmin) {
tmin=oc;
}
}
return tmin;
}
void cautaPunctDeIntalnire(int i, int j, int tstart, int tstop){
int k, iv, jv, oc,iCrt,jCrt;
DB printf("\ni=%d j=%d tstart=%d tstop=%d", i,j,tstart, tstop);
kPrim=kUltim=0;
treceInCoada(i,j);
oras[i][j]=-oras[i][j];
while (kPrim<kUltim) { // coada nu este vida
iCrt = extragePrimul(&jCrt);
oras[iCrt][jCrt] =-oras[iCrt][jCrt];
tstart=oras[iCrt][jCrt]-1;
DB printf("\n>>> icrt=%d jcrt=%d tstart=%d", iCrt,jCrt, tstart);
if(tstart) DB afismat("rjinit1.out");
if(tstart == tstop) {
if(iCrt<iIntalnire) {
iIntalnire=iCrt;
jIntalnire=jCrt;
}
if (iCrt==iIntalnire && jCrt<jIntalnire) {
jIntalnire=jCrt;
}
continue;
}
for(k=0;k<8;k++){
iv=iCrt+di[k];
if(iv<1||iv>N) continue;
jv=jCrt+dj[k];
if(jv<1||jv>M) continue;
oc=oras[iv][jv];
if(oc<0) continue;
if(oc==X) continue;
if(oc==tstart) {
treceInCoada(iv, jv);
oras[iv][jv]=-oc;
}
}
}
}
int copieOras[nMax+1][mMax+1];
int main()
{ int tmin;
citiremat("rj.in");
DB afismat("rjinit1.out");
for(int i=0;i<=N; i++)
for(int j=0; j<=M; j++)
copieOras[i][j]=oras[i][j];
distante(oras, iR,jR, iJ, jJ);
distante(copieOras, iJ,jJ, iR,jR);
DB afismat("rj.out");
tminDrum = timpminim(iJ,jJ);
tmin=(tminDrum+1)/2;
DB printf("\ntmin=%d",tminDrum);
cautaPunctDeIntalnire(iJ,jJ,tminDrum,tmin);
DB printf(" Intalnire=(%d, %d)",iIntalnire,jIntalnire);
ofstream out("rj.out");
out<< tmin+1 << " " <<iIntalnire<<" " <<jIntalnire;
DB printf("\n%d %d %d",tmin+1,iIntalnire,jIntalnire);
return 0;
}