Pagini recente » Cod sursa (job #1026343) | Cod sursa (job #255793) | Cod sursa (job #1332757) | Cod sursa (job #122326) | Cod sursa (job #280020)
Cod sursa(job #280020)
#include <stdio.h>
#define IN "rj.in"
#define OUT "rj.out"
#define N_MAX 1<<7
int tip,N,M;
int A[1<<7][1<<7],B[1<<7][1<<7];
char sir[1<<7];
struct que{int f,s;} Q[1<<13];
que r,jj;
const int xx[]={-1,-1,-1,0,0,1,1,1};
const int yy[]={-1,0,1,-1,1,-1,0,1};
void scan()
{
freopen(IN,"r",stdin);
freopen(OUT,"w",stdout);
scanf("%d%d\n",&N,&M);
int i,j;
for(i=1;i<=N;++i)
for(j=1;j<=M;++j)
A[i][j] = B[i][j] = 10101;
for(i=1;i<=N;++i)
{
fgets(sir,1<<7,stdin);
for(j=0;j<M;++j)
{
if(sir[j] == 'X')
A[i][j+1] = B[i][j+1] = -1;
if(sir[j] == 'R')
r.f = i,r.s = j+1;
if(sir[j] == 'J')
jj.f = i,jj.s = j+1;
}
}
}
int ok(int x,int y,int c)
{
if(x <0 || x>N || y<0 || y>M)
return 0;
if(!tip && A[x][y] <= c)
return 0;
if(tip && B[x][y] <= c)
return 0;
return 1;
}
void bf(que S)
{
int i,j,last = 0;
Q[++last] = S;
for(i=1;i<=last;++i)
{
int x = Q[i].f;
int y = Q[i].s;
int c = tip?B[x][y]+1:A[x][y]+1;
for(j=0;j<8;++j)
if( ok(x+xx[j],y+yy[j],c) )
{
Q[++last].f = x+xx[j];
Q[ last].s = y+yy[j];
if(!tip)
A[x+xx[j]][y+yy[j]] = c;
else
B[x+xx[j]][y+yy[j]] = c;
}
}
}
void solve()
{
A[r.f][r.s] = 0;
B[jj.f][jj.s] = 0;
tip = 0;
bf(r);
tip = 1;
bf(jj);
int i,j;
que rez;
rez.s = rez.f = 0;
A[0][0] = 10101;
for(i=1;i<=N;++i)
for(j=1;j<=M;++j)
if(A[i][j] == B[i][j] && A[rez.f][rez.s] > A[i][j] && A[i][j] != -1)
rez.f = i,rez.s = j;
printf("%d %d %d\n",A[rez.f][rez.s]+1,rez.f,rez.s);
}
int main()
{
scan();
solve();
return 0;
}