Cod sursa(job #258102)

Utilizator mika17Mihai Alex Ionescu mika17 Data 14 februarie 2009 18:31:58
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int NMAX = 100;
char A[NMAX][NMAX];
int tr[NMAX][NMAX],tj[NMAX][NMAX],N,M,lin[2],col[2],lmin,cmin,min,
 dl[] = {0,-1,-1,-1,0,1,1,1}, dc[] = {-1,-1,0,1,1,1,0,-1}; //de la vest

void readData() {

        freopen("rj.in","r",stdin);

        scanf("%d%d ",&N,&M);

        for(int i=0;i<N;++i)
        {
         gets(A[i]);

         char *t;
         for(int c='R',j=0;j<2;c='J',++j)
          if( (t = (char*)memchr(A[i],c,sizeof A[i])) )
            lin[j] = i, col[j] = t - A[i];
        }
}

inline bool valid(int l,int c)
{
        return l >= 0 && l < N && c >= 0 && c < M && A[l][c] == ' ';
}

void BF(int T[NMAX][NMAX],int w) {

        struct {int l,c;} Q[NMAX*NMAX];
        int le = 0,ri = 0;

        T[lin[w]][col[w]] = 1;

        Q[le] . l = lin[w], Q[le] . c = col[w];

        for(; le <= ri ; ++le)

           for(int d = 0, ll, cc; d < 8 ; ++d)
           {
            ll = Q[le] . l + dl[d], cc = Q[le] . c + dc[d];

            if(valid(ll,cc) && T[ ll ][ cc ] == -1)
            {
             T[ ll ][ cc ] = T[ Q[le] . l ][ Q[le] . c ] + 1;

             Q[++ri] . l = ll;
             Q[ri] . c = cc;
            }
           }
}

void getSol() {

        min = ~(1<<31);
        for(int i=0;i<N;++i)
         for(int j=0;j<M;++j)
            if(tr[i][j] != -1 && tr[i][j] == tj[i][j] && tr[i][j] < min)
              min = tr[i][j], lmin = i,cmin = j;
}

void writeData() {

        freopen("rj.out","w",stdout);
        printf("%d %d %d",min,lmin+1,cmin+1);
}

int main() {

        memset(tr,-1,sizeof tr);
        memset(tj,-1,sizeof tj);

        readData();
        BF(tr,0);
        BF(tj,1);
        getSol();
        writeData();
        return 0;
}