Cod sursa(job #78627)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 18 august 2007 18:41:50
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
/* Ivan Nicolae - Bucuresti */
/* InfoArena - Romeo si Julieta */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NMAX 101
#define ZERO 0
#define Infinity (0x3f3f3f3f)
#define _fin  "rj.in"
#define _fout "rj.out"

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

int i,j,n,m,rx,ry,jx,jy,R[NMAX][NMAX],J[NMAX][NMAX],min,ii,jj;
int c_x[NMAX*NMAX],c_y[NMAX*NMAX],c;
char x;

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

void Relax_Romeo(int x, int y)
{
 for (int i=0;i<=7;i++)
    {
     int xx=x+dx[i],yy=y+dy[i];
     if (Okay_Romeo(xx,yy) && R[x][y]+1<R[xx][yy])
       {
        R[xx][yy]=R[x][y]+1;
        c_x[++c]=xx; c_y[c]=yy;
       }
    }
}

void Lee_Romeo(int sx,int sy)
{
 c=0; c_x[++c]=sx; c_y[c]=sy;

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

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

void Relax_Julieta(int x, int y)
{
 for (int i=0;i<=7;i++)
    {
     int xx=x+dx[i],yy=y+dy[i];
     if (Okay_Julieta(xx,yy) && J[x][y]+1<J[xx][yy])
       {
        J[xx][yy]=J[x][y]+1;
        c_x[++c]=xx; c_y[c]=yy;
       }
    }
}

void Lee_Julieta(int sx,int sy)
{
 c=0; c_x[++c]=sx; c_y[c]=sy;

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

int main(void)
{
 freopen(_fin,"r",stdin);
 freopen(_fout,"w",stdout);

 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==' ')
	   {
	    R[i][j]=0;
	    J[i][j]=0;
	   }
	 if (x=='X')
	   {
	    R[i][j]=-1;
	    J[i][j]=-1;
	   }
	 if (x=='R')
	   {
	    rx=i; R[i][j]=0;
	    ry=j; J[i][j]=0;
	   }
         if (x=='J')
           {
            jx=i; R[i][j]=0;
            jy=j; J[i][j]=0;
           }
        }
     char eoln;
     gets("\n");
    }

 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    if (R[i][j] == 0)
      R[i][j]=Infinity;
 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    if (J[i][j] == 0)
      J[i][j]=Infinity;

 R[rx][ry]=J[jx][jy]=ZERO;

 Lee_Romeo(rx,ry);
 Lee_Julieta(jx,jy);

 min=Infinity;
 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    if (R[i][j] == J[i][j] && R[i][j]<min && R[i][j] > 0)
      { ii=i; jj=j; min=R[i][j]; }

 printf("%d %d %d",min+1,ii,jj);

 fclose(stdin);
 fclose(stdout);
 return 0;
}