Pagini recente » Cod sursa (job #1214842) | Cod sursa (job #2222027) | Cod sursa (job #2327145) | Cod sursa (job #3190779) | Cod sursa (job #1880532)
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int x[105][105]={0};
int z[105][105]={0};
int n,m,sti=105,stj=105,spi=105,spj=105;
int dl[8]= {-1,1,1,-1,0,1,0,-1};
int dc[8]= {1,1,-1,-1,1,0,-1,0};
int l;
char v[105][105];
void verif(int i,int j)
{
if (v[i][j]=='R')
{
sti=i;
stj=j;
}
else if (v[i][j]=='J')
{
spi=i;
spj=j;
}
if (sti!=105&&spi!=105)
return;
if (j==m)
verif(i+1,0);
else
verif(i,j+1);
}
void Lee1()
{
queue < pair < int, int > > coada;
coada.push(make_pair(sti,stj));
while (1)
{
int i=coada.front().first;
int j=coada.front().second;
coada.pop();
for (int k=0; k<4; k++)
{
int iu=i+dl[k];
int ju=j+dc[k];
if (v[iu][ju]==' '||v[iu][ju]=='J')
{
if (x[iu][ju]==0)
{
if (k==0)
{
if (v[iu][ju-1]==' '&&v[iu+1][ju]==' ')
{
x[iu][ju]=x[i][j]+1;
coada.push(make_pair(iu,ju));
}
}
else if (k==1)
{
if (v[iu-1][ju]==' '&&v[iu][ju-1]==' ')
{
x[iu][ju]=x[i][j]+1;
coada.push(make_pair(iu,ju));
}
}
else if (k==2)
{
if (v[iu][ju+1]==' '&&v[iu-1][ju]==' ')
{
x[iu][ju]=x[i][j]+1;
coada.push(make_pair(iu,ju));
}
}
else if (k==3)
{
if (v[iu][ju+1]==' '&&v[iu+1][ju]==' ')
{
x[iu][ju]=x[i][j]+1;
coada.push(make_pair(iu,ju));
}
}
}
}
if (v[iu][ju]=='J'&&x[iu][ju])
{
l=ceil(x[iu][ju]+1)/2;
return;
}
}
for (int k=4; k<8; k++)
{
int iu=i+dl[k];
int ju=j+dc[k];
if (v[iu][ju]==' '||v[iu][ju]=='J')
{
if (x[iu][ju]==0)
{
x[iu][ju]=x[i][j]+1;
coada.push(make_pair(iu,ju));
}
}
if (v[iu][ju]=='J'&&x[iu][ju])
{
l=ceil(x[iu][ju]+1)/2;
return;
}
}
}
}
void Lee2()
{
queue < pair < int,int > > coada2;
coada2.push(make_pair(spi,spj));
while (1)
{
int i=coada2.front().first;
int j=coada2.front().second;
coada2.pop();
for (int k=0; k<4; k++)
{
int iu=i+dl[k];
int ju=j+dc[k];
if (v[iu][ju]==' ')
{
if (z[iu][ju]==0)
{
if (k==0)
{
if (v[iu][ju-1]==' '&&v[iu+1][ju]==' ')
{
z[iu][ju]=z[i][j]+1;
coada2.push(make_pair(iu,ju));
}
}
else if (k==1)
{
if (v[iu-1][ju]==' '&&v[iu][ju-1]==' ')
{
z[iu][ju]=z[i][j]+1;
coada2.push(make_pair(iu,ju));
}
}
else if (k==2)
{
if (v[iu][ju+1]==' '&&v[iu-1][ju]==' ')
{
z[iu][ju]=z[i][j]+1;
coada2.push(make_pair(iu,ju));
}
}
else if (k==3)
{
if (v[iu][ju+1]==' '&&v[iu+1][ju]==' ')
{
z[iu][ju]=z[i][j]+1;
coada2.push(make_pair(iu,ju));
}
}
}
}
if (z[iu][ju]==x[iu][ju]&&x[iu][ju]==l)
{g<<iu+1<<' '<<ju+1<<' '<<l+1;
return;}
}
for (int k=4; k<8; k++)
{
int iu=i+dl[k];
int ju=j+dc[k];
if (v[iu][ju]==' ')
{
if (z[iu][ju]==0)
{
z[iu][ju]=z[i][j]+1;
coada2.push(make_pair(iu,ju));
}
}
if (z[iu][ju]==x[iu][ju]&&x[iu][ju]==l)
{g<<iu+1<<' '<<ju+1<<' '<<l+1;
return;}
}
}
}
int main()
{
int i;
f>>n>>m;
f.get();
for (i=0; i<n; i++)
f.getline(v[i],m+1);
verif(0,0);
Lee1();
Lee2();
return 0;
}