Pagini recente » Cod sursa (job #856197) | Cod sursa (job #2097538) | Cod sursa (job #1917127) | Cod sursa (job #1725807) | Cod sursa (job #298962)
Cod sursa(job #298962)
#include<cstdio>
#include<deque>
#define N 101
#define INF 100001
#define max(a,b) a>b ? a:b
#define IN freopen("rj.in","r",stdin)
#define OUT freopen("rj.out","w",stdout)
using namespace std;
int r[N][N],n,m,j[N][N];
char rd[N];
struct cd{
int x,y;
};
deque <cd> q;
cd ro,ju;
void cit()
{
scanf("%d%d\n",&n,&m);
for( int i=0 ; i<=n+1 ; ++i )
r[i][0]=j[i][0]=r[i][m+1]=j[i][m+1]=-1;
for( int i=0 ; i<=m+1 ; ++i )
r[0][i]=j[0][i]=r[n+1][i]=j[n+1][i]=-1;
for( int i=1 ; i<=n ; ++i )
{
fgets(rd+1,N-1,stdin);
//puts( rd+1 );
for( int k=1 ; k<=m ; ++k )
{
if( rd[k]=='X')
r[i][k]=j[i][k]=-1;
else if( rd[k]=='R')
{
ro.x=i;
ro.y=k;
}
else if(rd[k]=='J')
{
ju.x=i;
ju.y=k;
}
}
}
}
void m1( cd x )
{
cd z;
if( r[x.x-1][x.y]==0 )
{
z.x=x.x-1;
z.y=x.y;
q.push_back(z);
r[z.x][z.y]=r[x.x][x.y]+1;
}
if( r[x.x-1][x.y-1]==0 && j[x.x][x.y-1]>=0 && j[x.x-1][x.y]>=0 )
{
z.x=x.x-1;
z.y=x.y-1;
q.push_back(z);
r[z.x][z.y]=r[x.x][x.y]+1;
}
if( r[x.x-1][x.y+1]==0 && j[x.x][x.y+1]>=0 && j[x.x-1][x.y]>=0 )
{
z.x=x.x-1;
z.y=x.y+1;
q.push_back(z);
r[z.x][z.y]=r[x.x][x.y]+1;
}
if( r[x.x+1][x.y]==0 )
{
z.x=x.x+1;
z.y=x.y;
q.push_back(z);
r[z.x][z.y]=r[x.x][x.y]+1;
}
if( r[x.x+1][x.y-1]==0 && j[x.x][x.y-1]>=0 && j[x.x+1][x.y]>=0 )
{
z.x=x.x+1;
z.y=x.y-1;
q.push_back(z);
r[z.x][z.y]=r[x.x][x.y]+1;
}
if( r[x.x+1][x.y+1]==0 && j[x.x][x.y+1]>=0 && j[x.x+1][x.y]>=0 )
{
z.x=x.x+1;
z.y=x.y+1;
q.push_back(z);
r[z.x][z.y]=r[x.x][x.y]+1;
}
if( r[x.x][x.y-1]==0 )
{
z.x=x.x;
z.y=x.y-1;
q.push_back(z);
r[z.x][z.y]=r[x.x][x.y]+1;
}
if( r[x.x][x.y+1]==0 )
{
z.x=x.x;
z.y=x.y+1;
q.push_back(z);
r[z.x][z.y]=r[x.x][x.y]+1;
}
}
void m2( cd x )
{
cd z;
if( j[x.x-1][x.y]==0 )
{
z.x=x.x-1;
z.y=x.y;
q.push_back(z);
j[z.x][z.y]=j[x.x][x.y]+1;
}
if( j[x.x-1][x.y-1]==0 && j[x.x][x.y-1]>=0 && j[x.x-1][x.y]>=0 )
{
z.x=x.x-1;
z.y=x.y-1;
q.push_back(z);
j[z.x][z.y]=j[x.x][x.y]+1;
}
if( j[x.x-1][x.y+1]==0 && j[x.x][x.y+1]>=0 && j[x.x-1][x.y]>=0 )
{
z.x=x.x-1;
z.y=x.y+1;
q.push_back(z);
j[z.x][z.y]=j[x.x][x.y]+1;
}
if( j[x.x+1][x.y]==0 )
{
z.x=x.x+1;
z.y=x.y;
q.push_back(z);
j[z.x][z.y]=j[x.x][x.y]+1;
}
if( j[x.x+1][x.y-1]==0 && j[x.x][x.y-1]>=0 && j[x.x+1][x.y]>=0 )
{
z.x=x.x+1;
z.y=x.y;
q.push_back(z);
j[z.x][z.y]=j[x.x][x.y]+1;
}
if( j[x.x+1][x.y+1]==0 && j[x.x][x.y+1]>=0 && j[x.x+1][x.y]>=0 )
{
z.x=x.x+1;
z.y=x.y;
q.push_back(z);
j[z.x][z.y]=j[x.x][x.y]+1;
}
if( j[x.x][x.y-1]==0 )
{
z.x=x.x;
z.y=x.y-1;
q.push_back(z);
j[z.x][z.y]=j[x.x][x.y]+1;
}
if( j[x.x][x.y+1]==0 )
{
z.x=x.x;
z.y=x.y+1;
q.push_back(z);
j[z.x][z.y]=j[x.x][x.y]+1;
}
}
void bfs_r()
{
q.push_back(ro);
while(!q.empty())
{
m1(q.front());
q.pop_front();
}
}
void bfs_j()
{
q.push_back(ju);
while(!q.empty())
{
m2(q.front());
q.pop_front();
}
}
void ref()
{
for( int i=1 ; i<=n ; ++i )
for( int k=1 ; k<=m ; ++k )
if( j[i][k]!=r[i][k] || j[i][k]<=0 )
j[i][k]=INF;
}
void fin()
{
int min=INF;
cd rez;
for( int i=1 ; i<=n ; ++i )
for( int k=1 ; k<=m ; ++k )
if( j[i][k]<min )
{
rez.x=i;
rez.y=k;
min=j[i][k];
}
printf("%d %d %d\n",min,rez.x,rez.y);
}
int main()
{
IN;OUT;
cit();
bfs_r();
bfs_j();
ref();
fin();
return 0;
}