Cod sursa(job #108137)

Utilizator TabaraTabara Mihai Tabara Data 21 noiembrie 2007 17:26:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.93 kb
#include <fstream>
using namespace std;

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

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()
{
    ifstream fin ( in );
    
    fin >> n >> m;
    fin.get();
    int i, j;
    
    for ( i = 1; i <= n; ++i )
    {
          for ( j = 1; j <= m; ++j )
          {
              a[i][j] = fin.get();
              if ( a[i][j] == 'R' ) { ir = i, jr = j; }
              if ( a[i][j] == 'J' ) { ij = i, jj = j;  }              
              ro[i][j] = ju[i][j] = INF;
          }
          fin.get();
    }
    while ( !fin.eof() ) fin.get();
    fin.close();
    
    
    Lee1();
    Lee2();
    
    ofstream fout ( out );
    
    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;
                           }
                      } 
                 }
        }
    }
       
    fout << minim << " " << pozi << " " << pozj;// << "\n";
    fout.close();
    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] == 'X' ) 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] == 'X' ) return 0;
    if ( ju[i][j] < INF ) return 0;
    return 1;
}