Cod sursa(job #76021)

Utilizator FlorianFlorian Marcu Florian Data 7 august 2007 16:24:16
Problema Rj Scor Ascuns
Compilator cpp Status done
Runda Marime 1.53 kb
#include <stdio.h>
#include <string>

#define maxn 110
#define maxx 10010
#define maxl 8

int n,m,l,px,py;
char a[maxn][maxn];
int c[maxn][maxn],d[maxn][maxn];
int sx[maxx],sy[maxx];
int dirx[maxl]={0,1,1,1,0,-1,-1,-1};
int diry[maxl]={-1,-1,0,1,1,1,0,-1};

void BFS(int x,int y,int c[][maxn])
{
     int i,j,cx,cy;
     
     for (i=1;i<=n;i++)
       for (j=0;j<m;j++) 
         if (a[i][j]=='X') c[i][j]=-1;
         else c[i][j]=maxx;
         
     l=1;
     sx[l]=x;
     sy[l]=y;
     c[x][y]=1;
     for (i=1;i<=l;i++)
       for (j=0;j<maxl;j++)
       {
           cx=sx[i]+dirx[j];
           cy=sy[i]+diry[j];
           
           if ((cx>0) && (cx<=n) && (cy>=0) && (cy<=m) && (c[sx[i]][sy[i]]+1<c[cx][cy]))
           {
               l++;
               sx[l]=cx;
               sy[l]=cy;
               c[cx][cy]=c[sx[i]][sy[i]]+1;
           }
       }
}

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    
    scanf("%d %d ",&n,&m);
    
    int i,j;
    
    for (i=1;i<=n;i++) fgets(a[i],maxn,stdin);
    
    for (i=1;i<=n;i++)
      for (j=0;j<m;j++) 
        if (a[i][j]=='R') BFS(i,j,c);
        
    for (i=1;i<=n;i++)
      for (j=0;j<m;j++)
        if (a[i][j]=='J') BFS(i,j,d);
        
    px=py=0;
    c[px][py]=maxx;
        
    for (i=1;i<=n;i++)
      for (j=0;j<m;j++)
        if ((c[i][j]!=-1) && (c[i][j]==d[i][j]) && (c[i][j]<c[px][py])) px=i,py=j;
        
    printf("%d %d %d\n",px,py+1,c[px][py]);
    
    return 0;
}