Pagini recente » Cod sursa (job #1269119) | Cod sursa (job #2446240) | Cod sursa (job #2522674) | Cod sursa (job #727927) | Cod sursa (job #1900878)
#include<bits/stdc++.h>
#define maxN 105
using namespace std;
deque<pair<int,int> > q;
int rx,ry,jx,jy,a[maxN][maxN],Romeo[maxN][maxN],Julieta[maxN][maxN],n,m,isol,jsol;
int d[100][5];
char s[105];
void Initializare()
{
d[1][1]=-1;
d[1][2]=-1;
d[2][1]=-1;
d[2][2]=0;
d[3][1]=-1;
d[3][2]=1;
d[4][1]=0;
d[4][2]=-1;
d[5][1]=0;
d[5][2]=1;
d[6][1]=1;
d[6][2]=-1;
d[7][1]=1;
d[7][2]=0;
d[8][1]=1;
d[8][2]=1;
}
void Lee1()
{
int n1,n2,nr1,nr2;
q.clear();
q.push_front({rx,ry});
while(!q.empty())
{
n1=q.front().first;
n2=q.front().second;
for(int i=1;i<=8;i++)
{
nr1=n1+d[i][1];
nr2=n2+d[i][2];
if(!a[nr1][nr2])
{
if( (Romeo[nr1][nr2]>(1+Romeo[n1][n2])))
{
Romeo[nr1][nr2]=1+Romeo[n1][n2];
q.push_back({nr1,nr2});
}
}
}
q.pop_front();
}
}
void Lee2()
{
int n1,n2,nr1,nr2;
q.clear();
q.push_front({jx,jy});
while(!q.empty())
{
n1=q.front().first;
n2=q.front().second;
for(int i=1;i<=8;i++)
{
nr1=n1+d[i][1];
nr2=n2+d[i][2];
if(!a[nr1][nr2])
{
if((Julieta[nr1][nr2]>(1+Julieta[n1][n2])))
{
Julieta[nr1][nr2]=(1+Julieta[n1][n2]);
q.push_back({nr1,nr2});
}
}
}
q.pop_front();
}
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
scanf("%d%d",&n,&m);
Initializare();
for(int i=0;i<=(m+1);i++)
{
a[0][i]=a[n+1][i]=-1;
}
for(int i=0;i<=(n+1);i++)
{
a[i][0]=a[i][m+1]=-1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
Romeo[i][j]=Julieta[i][j]=100000;
}
}
for(int i=1;i<=n;i++)
{
scanf("\n");
fread(s,1,m,stdin);
for(int j=0;j<m;j++)
{
if(s[j]=='R')
{
rx=i;
ry=j+1;
}
else
if(s[j]=='J')
{
jx=i;
jy=j+1;
}
else
if(s[j]=='X')
{
a[i][j+1]=-1;
}
else
if(s[j]==' ') a[i][j+1]=0;
}
}
Romeo[rx][ry]=1;
Julieta[jx][jy]=1;
Lee1();
Lee2();
int minim=10000;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(Romeo[i][j]==Julieta[i][j])
{
if(Julieta[i][j]<minim)
{
minim=Julieta[i][j];
isol=i;
jsol=j;
}
}
printf("%d %d %d\n",minim,isol,jsol);
return 0;
}