Pagini recente » ONIS 2015, Solutii Runda 1 | Monitorul de evaluare | ONIS 2015, Solutii Runda 1 | ONIS 2015, Solutii Runda 1 | Cod sursa (job #1874495)
#include <bits/stdc++.h>
using namespace std;
int n,m,xs2,ys2,xs1,ys1,nr[103][103],nr2[103][103],xf,yf,Min;
int a[103][103];
short dx[]={-1,-1,0,1,1,1,0,-1};
short dy[]={0,1,1,1,0,-1,-1,-1};
char c,s[1001];
void af(int a[103][103])
{
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d ",a[i][j]);
printf("\n");
}
}
struct meh{
int c;
int l;
}x,y;
queue <meh> q;
void bordare()
{
for(int i=0;i<=n+1;i++)
a[i][0]=a[i][m+1]=1;
for(int j=0;j<=m+1;j++)
a[0][j]=a[n+1][j]=1;
}
void lee(int nr[103][103])
{
int k,lv,cv;
while(!q.empty())
{
x=q.front();
q.pop();
for(k=0;k<8;k++)
{
lv=dx[k]+x.l;
cv=dy[k]+x.c;
if(a[lv][cv]==0 && nr[lv][cv]>nr[x.l][x.c]+1)
{
y.l=lv;
y.c=cv;
q.push(y);
nr[lv][cv]=nr[x.l][x.c]+1;
}
}
}
}
void cit()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
}
int main()
{
cit();
scanf("%d %d",&n,&m);
gets(s);
for(int i=1;i<=n;i++)
{
gets(s);
for(int j=0;j<m;j++){
c=s[j];
if(c=='R'){
xs1=i;
ys1=j+1;
}
else if(c=='J')
{
xs2=i;
ys2=j+1;
}
else if(c=='X')
a[i][j+1]=1;
nr[i][j+1]=999999;
nr2[i][j+1]=999999;
}
}
bordare();
nr[xs1][ys1]=1;
nr2[xs2][ys2]=1;
x.l=xs1;x.c=ys1;
q.push(x);
lee(nr);
x.l=xs2;x.c=ys2;
q.push(x);
lee(nr2);
//af(a);
Min=99999999;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(nr[i][j]==nr2[i][j] && nr[i][j]<Min)
{
Min=nr[i][j];
xf=i;
yf=j;
}
printf("%d %d %d\n",Min,xf,yf);
// af(nr2);
return 0;
}