Pagini recente » Cod sursa (job #107605) | Cod sursa (job #2896177) | Cod sursa (job #2644527) | Cod sursa (job #857423) | Cod sursa (job #298903)
Cod sursa(job #298903)
#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 ver()
{
char romeo='R',julieta='J';
for( int i=0 ; i<=n+1 ; ++i,printf("\n") )
for( int k=0 ; k<=m+1 ; ++k )
if( ro.x==i && ro.y==k )
printf("%3c",romeo);
else if( ju.x==i && ju.y==k)
printf("%3c",julieta);
else
printf("%3d",j[i][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]==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][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]==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]=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]>0 && 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();
//ver();
fin();
return 0;
}