Pagini recente » Cod sursa (job #1284566) | Cod sursa (job #2683377) | Cod sursa (job #3126840) | Cod sursa (job #2382837) | Cod sursa (job #2133340)
#include <fstream>
#include <queue>
#include <cstring>
#define LMax 100
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
const int dx[]={1, -1, 1, -1, 0, 1, 0, -1};
const int dy[]={1, -1, -1, 1, 1, 0, -1, 0};
int n, m, Oras[LMax+5][LMax+5];
int rx, ry, jx, jy;
int l=101, c=101, d=10100;
bool Vizitat[LMax+5][LMax+5];
queue < pair < int, int > > coada;
void Bordare ()
{
for(int i=0;i<=n+1;i++)
{
Vizitat[i][0]=-1;
Vizitat[i][m+1]=-1;
}
for(int j=0;j<=m+1;j++)
{
Vizitat[0][j]=-1;
Vizitat[n+1][j]=-1;
}
}
void LeeR (int x, int y)
{
coada.push(make_pair(x,y));
Vizitat[x][y]=1;
while(!coada.empty())
{
int i=coada.front().first;
int j=coada.front().second;
coada.pop();
for(int dir=0;dir<8;dir++)
{
int i_new=i+dx[dir];
int j_new=j+dy[dir];
if(!Vizitat[i_new][j_new])
{
Oras[i_new][j_new]=Oras[i][j]+1;
Vizitat[i_new][j_new]=1;
coada.push(make_pair(i_new,j_new));
}
}
}
Oras[jx][jy]=0;
}
void LeeJ (int x, int y)
{
memset(Vizitat, 0, sizeof Vizitat);
coada.push(make_pair(x,y));
Vizitat[x][y]=1;
while(!coada.empty())
{
int i=coada.front().first;
int j=coada.front().second;
coada.pop();
for(int dir=0;dir<8;dir++)
{
int i_new=i+dx[dir];
int j_new=j+dy[dir];
if(!Vizitat[i_new][j_new])
{
Vizitat[i_new][j_new]=1;
int aux=Oras[i][j]+1;
if(aux<=Oras[i_new][j_new])
{
if(aux<Oras[i_new][j_new])
{
Oras[i_new][j_new]=aux;
coada.push(make_pair(i_new,j_new));
}
else
{
if(aux<=d)
{
if(aux<d)
{
d=aux;
l=i_new;
c=j_new;
}
else
{
if(i_new<=l)
{
if(i_new<l)
{
l=i_new;
c=j_new;
}
else
{
if(j_new<c)
{
int l=i_new;
int c=j_new;
}
}
}
}
}
}
}
}
}
}
}
int main ()
{
fin>>n>>m;
for(int i=1;i<=n;i++)
{
char x[102];
fin.get();
fin.get(x,102);
for(int j=0;j<m;j++)
{
if(x[j]=='X')
Vizitat[i][j+1]=1;
else if(x[j]=='R')
{
rx=i;
ry=j+1;
}
else if(x[j]=='J')
{
jx=i;
jy=j+1;
}
}
}
Bordare ();
LeeR (rx,ry);
LeeJ (jx, jy);
fout<<d+1<<' '<<l<<' '<<c;
}