Cod sursa(job #117099)

Utilizator TabaraTabara Mihai Tabara Data 20 decembrie 2007 18:15:19
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.44 kb
#include <stdio.h>

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

const int di[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dj[] = { 0, 1, 1, 1, 0, -1, -1, -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 Ok1(int,int);
int Ok2(int,int);
void Lee1();
void Lee2();

int main()
{
    FILE *fin = fopen( in, "r" );
    FILE *fout = fopen( out, "w" );
    
    int i, j;
    fscanf( fin, "%d%d\n", &n, &m );
    char linie[110];
    for ( i = 1; i <= n; ++i )
    {
        fgets( linie, 110, fin );
        int j = 0;
        while ( j < m )
        {
              if ( linie[j] == 'R' ) ir = i, jr = j+1, a[i][j+1] = -1;
              else if ( linie[j] == 'J' ) ij = i, jj = j + 1, a[i][j+1] = -1;
              else if ( linie[j] == 'X' ) a[i][j+1] = -1;
              else if ( linie[j] == ' ' ) a[i][j+1] = 1;
              j++;
        }
    }
    
    for ( i = 1; i <= n; ++i )
        for ( j = 1; j <= m; ++j )
            ro[i][j] = ju[i][j] = INF;
            
    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;
    pozi = pozj = NMAX;
    for ( i = 1; i <= n; ++i )
    {
        for ( j = 1; j <= m; ++j )
        {                    
                 if ( ro[i][j] == ju[i][j] )
                 {
                      if ( ro[i][j] < minim ) 
                      {
                           minim = ro[i][j] + 1;
                           pozi = i;
                           pozj = j;
                      }
                      if ( ro[i][j] == minim )
                      {
                           if ( i < pozi ) 
                           {
                                pozi = i;
                                pozj = j;
                           }
                           if ( i == pozi && j < pozj )
                           {
                                pozi = i;
                                pozj = j;
                           }
                      } 
                 }
        }
    }
       
    fprintf( fout, "%d %d %d\n", minim, pozi, pozj );
    return 0;
}
              
void Lee1()
{
     ro[ir][jr] = 0;
     prim = ultim = 0;
     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[d];
               if ( Ok1(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 = 0;
     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[d];
               if ( Ok2(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 Ok1( int i, int j )
{
    if ( i < 1 || i > n || j < 1 || j > m ) return 0;
    if ( a[i][j] == -1 ) return 0;
    if ( ro[i][j] < INF ) return 0;
    return 1;
} 

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