Cod sursa(job #78611)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 18 august 2007 17:16:36
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 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*4],c_y[NMAX*NMAX*4],c;
char row;

int Okay_Romeo(int x, int y)
{
 if (x < 1 || x > n || y < 1 || y > m)
   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;
 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++)
        {
         scanf("%c",&row);
         if (row=='R')
           { rx=i; ry=j; R[i][j]=Infinity; J[i][j]=Infinity;}
           else
         if (row=='J')
           { jx=i; jy=j; R[i][j]=Infinity; J[i][j]=Infinity;}
           else
         if (row=='X')
           { R[i][j]=-1; J[i][j]=-1; }
           else
         if (row==' ')
           { R[i][j]=Infinity; J[i][j]=Infinity; }
        }
     scanf("\n");
    }

 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\n",min+1,ii,jj);

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