Pagini recente » Cod sursa (job #2250191) | Cod sursa (job #581218) | Cod sursa (job #1937156) | Cod sursa (job #2241385) | Cod sursa (job #299061)
Cod sursa(job #299061)
#include<cstdio>
#include<deque>
#define INF 10005
#define N 105
using namespace std;
struct cd{
int x,y;
};
int r[N][N],j[N][N],n,m;
char s[N];
cd R,J;
deque <cd> q;
void cit()
{
scanf("%d%d\n",&n,&m);
for( int i=0 ; i<=m+1 ; ++i )
r[0][i]=r[n+1][i]=j[0][i]=j[n+1][i]=-1;
for( int i=0 ; i<=n+1 ; ++i )
r[i][0]=r[i][m+1]=j[i][0]=j[i][m+1]=-1;
for( int i=1 ; i<=n ; ++i )
{
fgets(s+1,N-1,stdin);
for( int k=1 ; k<=m ; ++k )
if(s[k]=='X')
r[i][k]=j[i][k]=-1;
else if(s[k]=='R')
{
R.x=i;
R.y=k;
}
else if(s[k]=='J')
{
J.x=i;
J.y=k;
}
}
}
void ver()
{
char ch='X';
for( int i=0 ; i<=n+1 ; ++i,printf("\n") )
for( int k=0 ; k<=m+1 ; ++k )
if(j[i][k]==INF)
printf("%3c",ch);
else
printf("%3d",j[i][k]);
}
void m_r( cd x )
{
cd z;
if( r[x.x-1][x.y-1]==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 )
{
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;
}
if( r[x.x+1][x.y-1]==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 )
{
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;
}
}
void m_j( cd x )
{
cd z;
if( j[x.x-1][x.y-1]==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 )
{
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][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;
}
if( j[x.x+1][x.y-1]==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 )
{
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;
}
}
void bfs_r()
{
q.push_back(R);
while(!q.empty())
{
m_r(q.front());
q.pop_front();
}
}
void bfs_j()
{
q.push_back(J);
while(!q.empty())
{
m_j(q.front());
q.pop_front();
}
}
void ref()
{
for( int i=1 ; i<=n ; ++i )
for( int k=1 ; k<=m ; ++k )
if( r[i][k]!=j[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 )
{
min=j[i][k];
rez.x=i;
rez.y=k;
}
printf("%d %d %d\n",1+min,rez.x,rez.y);
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
cit();
bfs_r();
bfs_j();
ref();
ver();
fin();
return 0;
}