Cod sursa(job #474635)

Utilizator elfusFlorin Chirica elfus Data 4 august 2010 14:52:05
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<stdio.h>
#include<string.h>
int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
int a[105][105],b[105][105];
struct elf
{
int x,y;
};
elf q[10010];
int main()
{
int n,m,i,j,xa,ya,xb,yb;
char ch;
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
xa=ya=xb=yb=-1;
scanf("%d%d\n",&n,&m);
for(i=0;i<=n+1;i++)
  a[i][0]=a[i][m+1]=b[i][0]=b[i][m+1]=-1;
for(i=0;i<=m+1;i++)
  a[0][i]=a[n+1][i]=b[0][i]=b[n+1][i]=-1;
for(i=1;i<=n;i++)
  {
  for(j=1;j<=m;j++)
    {
    scanf("%c",&ch);
    if(ch=='R')
     { xa=i; ya=j;a[xa][ya]=1; b[i][j]=-2; }
    if(ch=='J')
     { xb=i; yb=j;b[xb][yb]=1; a[i][j]=-2; }
    if(ch==' ')
     { a[i][j]=b[i][j]=-2; }
    if(ch=='X')
     { a[i][j]=b[i][j]=-1; }
    }
  scanf("%c",&ch);
  }
int p,u=p=1,xn,yn;
xn=yn=-1;
q[1].x=xa; q[1].y=ya;
while(p<=u)
 {
 for(i=0;i<=7;i++)
  {
  xn=q[p].x+dx[i];
  yn=q[p].y+dy[i];
  if(a[xn][yn]!=-1)
  if(a[xn][yn]==-2 || a[q[p].x][q[p].y]+1<a[xn][yn])
    {a[xn][yn]=a[q[p].x][q[p].y]+1; q[++u].x=xn; q[u].y=yn; }
  }
 p++;
 }
memset(q,0,sizeof(q));
p=u=1; q[1].x=xb; q[1].y=yb;
while(p<=u)
 {
 for(i=0;i<=7;i++)
  {
  xn=q[p].x+dx[i];
  yn=q[p].y+dy[i];
  if(b[xn][yn]!=-1)
  if(b[xn][yn]==-2 || b[q[p].x][q[p].y]+1<b[xn][yn])
    {b[xn][yn]=b[q[p].x][q[p].y]+1; q[++u].x=xn; q[u].y=yn; }
  }
 p++;
 }
int min=n*m+2012,xm,ym;
xm=ym=-1;
for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
    if(a[i][j]==b[i][j] && a[i][j]<min && a[i][j]>-1)
      {min=a[i][j]; xm=i; ym=j;}
printf("%d %d %d",min,xm,ym);
return 0;
}