Cod sursa(job #107985)

Utilizator TabaraTabara Mihai Tabara Data 20 noiembrie 2007 23:29:58
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <stdio.h>

#define in "rj.in"
#define out "rj.out"
#define NMAX 101
#define INF 30001

const int di[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
const int dj[] = { 1, 1, 0, -1, -1, -1, 0, 1 };

char a[NMAX][NMAX];
int n, m;
int ro[NMAX][NMAX];
int ju[NMAX][NMAX];
int ir, jr, ij, jj;
int iv, jv, pozi, pozj;

int q[NMAX*NMAX][2];
int prim, ultim;

int Ok(int,int);
void Lee1();
void Lee2();

int main()
{
    freopen( in, "r", stdin );
    freopen( out, "w", stdout );
    
    scanf( "%d %d\n", &n, &m );
    int i, j;
    char c;
    for ( i = 1; i <= n; ++i )
          for ( j = 1; j <= m; ++j )
          {
              scanf( "%c", &c);
              if ( j == m ) scanf( "\n" );
              if ( c == 'R' ) { ir = i, jr = j; }
              if ( c == 'J' ) { ij = i, jj = j; }
              if ( c == ' ' ) a[i][j] = 1;
              if ( c == 'X' ) a[i][j] = -1;
              ro[i][j] = ju[i][j] = INF;
          }
    /*for ( i = 1; i <= n; ++i )
    {
          for ( j = 1; j <= m; ++j )
              printf( "%d ", a[i][j]);      
          printf( "\n");
    }*/
    Lee1();
    Lee2();
    /*
    for ( i = 1; i <= n; ++i )
    {
          for ( j = 1; j <= m; ++j )
              printf( "%d ", ro[i][j]);      
          printf( "\n");
    }
    
    printf( "\n");printf( "\n");printf( "\n");
    
    for ( i = 1; i <= n; ++i )
    {
          for ( j = 1; j <= m; ++j )
              printf( "%d ", ju[i][j]);      
          printf( "\n");
    } */
    int minim = INF;
    for ( i = 1; i <= n; ++i )
    {
        for ( j = 1; j <= m; ++j )
        {
            if ( Ok(i,j) )
            {
                 if ( ro[i][j] == ju[i][j] )
                 {
                      if ( ro[i][j] < minim ) 
                      {
                           minim = ro[i][j];
                           pozi = i;
                           pozj = j;
                      }
                 }
            }
        }
    }
       
    printf( "%d %d %d\n", minim+1, pozi, pozj );
    return 0;
}
              
void Lee1()
{
     ro[ir][jr] = 0;
     prim = ultim = 1;
     q[prim][0] = ir;
     q[prim][1] = jr;
     
     int i, j, d;
     
     while ( prim <= ultim )
     {
           for ( d = 0; d < 8; ++d )
           {
               i = q[prim][0];
               j = q[prim][1];
               iv = i + di[d];
               jv = j + dj[j];
               if ( Ok(iv,jv) )
               {
                    if ( ro[iv][jv] > ro[i][j] + 1 )
                    {
                         ro[iv][jv] = ro[i][j] + 1;
                         ultim++;
                         q[ultim][0] = iv;
                         q[ultim][1] = jv;
                    }
               }
           }
           prim++;
     }                 
}

void Lee2()
{
     ju[ij][jj] = 0;
     prim = ultim = 1;
     q[prim][0] = ij;
     q[prim][1] = jj;
     
     int i, j, d;
     
     while ( prim <= ultim )
     {
           for ( d = 0; d < 8; ++d )
           {
               i = q[prim][0];
               j = q[prim][1];
               iv = i + di[d];
               jv = j + dj[j];
               if ( Ok(iv,jv) )
               {
                    if ( ju[iv][jv] > ju[i][j] + 1 )
                    {
                         ju[iv][jv] = ju[i][j] + 1;
                         ultim++;
                         q[ultim][0] = iv;
                         q[ultim][1] = jv;
                    }
               }
           }
           prim++;
     }                 
}


int Ok( int i, int j )
{
    if ( i < 1 || i > n || j < 1 || j > m ) return 0;
    if ( a[i][j] == -1 ) return 0;
    return 1;
}