Cod sursa(job #281175)

Utilizator moonbeamElma Moonbeam moonbeam Data 13 martie 2009 21:14:17
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<stdio.h>
#define N 105
const int dx[]={0,0,1,-1,1,-1,-1,1};
const int dy[]={1,-1,0,0,1,-1,1,-1};
char s[N][N];
int n,m,a[N][N],b[N][N];
void bfsj(int x1[2])
{
  int coada[N*N][2],x[2],y[2],u=0,p=0;
  coada[u][0]=x1[0];
  coada[u++][1]=x1[1];
  b[x1[0]][x1[1]]=1;
  while (u!=p)
  {
    x[0]=coada[p][0];
    x[1]=coada[p++][1];
    for (int i=0; i<8; ++i)
    {
      y[0]=x[0]+dx[i];
      y[1]=x[1]+dy[i];
      if (b[y[0]][y[1]]==0)
      {
	coada[u][0]=y[0];
	coada[u++][1]=y[1];
	b[y[0]][y[1]]=1+b[x[0]][x[1]];
      }
    }
  }
}
void bfsr(int x1[2])
{
  int coada[N*N][2],x[2],y[2],u=0,p=0;
  coada[u][0]=x1[0];
  coada[u++][1]=x1[1];
  a[x1[0]][x1[1]]=1;
  while (u!=p)
  {
    x[0]=coada[p][0];
    x[1]=coada[p++][1];
    for (int i=0; i<8; ++i)
    {
      y[0]=x[0]+dx[i];
      y[1]=x[1]+dy[i];
      if (a[y[0]][y[1]]==0)
      {
	coada[u][0]=y[0];
	coada[u++][1]=y[1];
	a[y[0]][y[1]]=1+a[x[0]][x[1]];
      }
    }
  }
}
void citire()
{
  freopen("rj.in","r",stdin);
  freopen("rj.out","w",stdout);
  scanf("%d%d\n",&n,&m);
  for (int i=0; i<=n+1; ++i)
  {
    b[i][0]=b[i][m+1]=a[i][0]=a[i][m+1]=-1;
  }
  for (int i=0; i<=m+1; ++i)
  {
    b[n+1][i]=b[0][i]=a[n+1][i]=a[0][i]=-1;
  }
  for (int i=1; i<=n; ++i)
      fgets(1+s[i],N,stdin);
  int x[2],y[2];
  for (int i=1; i<=n; ++i)
     for (int j=1; j<=m; ++j)
     {
       if (s[i][j]=='R')
       {
	 x[0]=i;
	 x[1]=j;
       }
       else
       if (s[i][j]=='J')
       {
       y[0]=i;
       y[1]=j;
       }
       else
       if (s[i][j]=='X')
	  b[i][j]=a[i][j]=-1;
     }
  bfsr(x);
  bfsj(y);
  int min=10000;
  int x1,y1;
  for (int i=1; i<=n; ++i)
  {
    for (int j=1;j<=m; ++j)
    if (a[i][j]==b[i][j]&&a[i][j]>0&&a[i][j]<min)
    {
      min=a[i][j];
      x1=i;
      y1=j;
    }
  }
  printf("%d %d %d",min,x1,y1);
  /*for (int i=1; i<=n; ++i)
  {
    for (int j=1; j<=m; ++j)
      printf("%d ",a[i][j]);
    printf("\n");
  }
  printf("\n");
  for (int i=1; i<=n; ++i)
  {
    for (int j=1; j<=m; ++j)
      printf("%d ",b[i][j]);
    printf("\n");
  }*/
}
int main()
{
  citire();
  return 0;
}