Cod sursa(job #78544)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 18 august 2007 14:31:54
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
/* Ivan Nicolae - Bucuresti */
/* Romeo si Julieta - Oji 2004 cls X-a */
#include <stdio.h>
#include <stdlib.h>

#define NMAX (100+2)
#define Infinity (2*0x3f3f)
#define _fin  "rj.in"
#define _fout "rj.out"

int dx[] = {-1,+1,-0,+0,-1,+1,+1,-1};
int dy[] = {-0,+0,-1,+1,+1,-1,+1,-1};

int i,j,n,m,A[NMAX][NMAX], B[NMAX][NMAX],c,rx,ry,jx,jy;
int *c_x,* c_y;

void AlocaMemorie(void);
void ReadData(void);
int  Okay(int, int);

void FillWithA(int ce)
{
 for (int i=1;i<=n;i++)
 for (int j=1;j<=m;j++)
    if (A[i][j] != -1)
      A[i][j]=ce;
}

void FillWithB(int ce)
{
 for (int i=1;i<=n;i++)
 for (int j=1;j<=m;j++)
    if (B[i][j] != -1)
      B[i][j]=ce;
}

void Relax_A(int x, int y)
{
 int i;
 for (i=0;i<=7;i++)
    {
     int xx=x+dx[i], yy=y+dy[i];
     if (Okay(xx,yy))
       {
	if (A[xx][yy] > A[x][y] + 1)
	  {
	   A[xx][yy] = A[x][y] + 1;
	   c_x[++c]=xx; c_y[c]=yy;
	  }
       }
    }
}

void Relax_B(int x, int y)
{
 int i;
 for (i=0;i<=7;i++)
    {
     int xx=x+dx[i], yy=y+dy[i];
     if (Okay(xx,yy))
       {
	if (B[xx][yy] > B[x][y] + 1)
	  {
	   B[xx][yy] = B[x][y] + 1;
	   c_x[++c]=xx; c_y[c]=yy;
	  }
       }
    }
}

void LeeA(int sx, int sy)
{
 FillWithA(Infinity);
 A[sx][sy]=0; c=0;
 c_x[++c]=sx; c_y[c]=sy;

 int i;
 for (i=1;i<=c;i++)
    Relax_A(c_x[i],c_y[i]);
}

void LeeB(int sx, int sy)
{
 FillWithB(Infinity);
 B[sx][sy]=0; c=0;
 c_x[++c]=sx; c_y[c]=sy;

 int i;
 for (i=1;i<=c;i++)
    Relax_B(c_x[i],c_y[i]);
}

void PrintData(void)
{
 freopen(_fout,"w",stdout);
 int i,j,r_x,r_y,r_d=Infinity;

 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    if (A[i][j] == B[i][j] && A[i][j] < r_d && A[i][j] != -1)
      { r_d=A[i][j]; r_x=i; r_y=j; }

 printf("%d %d %d\n",r_d+1,r_x,r_y);
 fclose(stdin);
}

int main()
{
 AlocaMemorie();
 ReadData();
 LeeA(rx,ry);
 LeeB(jx,jy);
 PrintData();

 return 0;
}

void AlocaMemorie(void)
{
 c_x = (int*) malloc(sizeof(int)*NMAX*NMAX);
 c_y = (int*) malloc(sizeof(int)*NMAX*NMAX);
}

void ReadData(void)
{
 int i,j;
 freopen(_fin,"r",stdin);
 scanf("%d %d\n",&n,&m);
 for (i=1;i<=n;i++)
    {
     for (j=1;j<=m;j++)
	{
	 char x;
	 scanf("%c",&x);
	 if (x==' ')
	   {
	    A[i][j]=0;
	    B[i][j]=0;
	   }
	 if (x=='X')
	   {
	    A[i][j]=-1;
	    B[i][j]=-1;
	   }
	 if (x=='R')
	   {
	    rx=i; A[i][j]=0;
	    ry=j; B[i][j]=0;
	   }
	 if (x=='J')
	   {
	    jx=i; A[i][j]=0;
	    jy=j; B[i][j]=0;
	   }
	}
     char eoln;
     gets("\n");
    }
 fclose(stdin);
}

int Okay(int x, int y)
{
 if (x < 1 || x > n || y < 1 || y > m)
   return 0;
 if (A[x][y] == -1)
   return 0;
 return 1;
}