Cod sursa(job #553755)

Utilizator david_raucaRauca Ioan David david_rauca Data 14 martie 2011 12:17:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include<fstream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f

ifstream fin("rj.in");
ofstream fout("rj.out");

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

int n, m;
int ir, jr, ij, jj;
int v;

queue<pair<int, int> > Q;

char G[105][105];
int r[105][105];
int j[105][105];

void Read();
void BF( int x, int y );
void Solve();
bool OK( int i, int j);
void Write();

int main()
{
    Read();
    Solve();
    
    fin.close();
    fout.close();
    
    return 0;
}

void Read()
{
     fin >> n >> m;
     fin.get();
     char aux[101];
     for( int i = 0; i < n; ++i )
     {
          fin.getline( aux, 101, '\n' );
          strcpy( G[i], aux );
     }
     
     for( int i = 0; i < n; i++ )
          for( int j2 = 0; j2 < m; j2++ )
          {
               if( G[i][j2] == 'R' )
               {
                   ir = i;
                   jr = j2;
               }
               if( G[i][j2] == 'J' )
               {
                   ij = i;
                   jj = j2;
               }
               
               r[i][j2] = j[i][j2] = INF;
          }
}

void Solve()
{
     v = 1;
     BF( ir, jr );
     v = 2;
     BF( ij, jj );
     Write();
}

void BF( int x, int y )
{
     Q.push( make_pair( x, y ) );
     
     if( v == 1 )
         r[x][y] = 1;
     else
         j[x][y] = 1;
         
     pair< int, int > p;
     
     while( !Q.empty() )
     {
            p = Q.front();
            for( int d = 0; d < 8; ++d )
            {
                 int iv = p.first + di[d];
                 int jv = p.second + dj[d];
                 if( OK( iv, jv ) )
                 {
                     if( v == 1 && r[iv][jv] > r[ p.first ][ p.second ] + 1 )
                     {
                         r[iv][jv] = r[ p.first ][ p.second ] + 1;
                         Q.push( make_pair( iv, jv ) );
                     }
                     if( v != 1 && j[iv][jv] > j[ p.first ][ p.second ] )
                     {
                         j[iv][jv] = j[ p.first ][ p.second ] + 1;
                         Q.push( make_pair( iv, jv ) );
                     }
                 }
            }
            Q.pop();
     }
}

bool OK( int i, int j )
{
     if( i < 0 || i >= n || j < 0 || j >= m || G[i][j] == 'X' || G[i][j] == 'J' || G[i][j] == 'R' )
         return false;
     return true;
}

void Write()
{
     int i1, j1, minim = INF;
     for( int i = 0; i < n; ++i )
          for( int j2 = 0; j2 < m; ++j2 )
               if( j[i][j2] == r[i][j2] && minim > r[i][j2] )   
               {
                   i1 = i;
                   j1 = j2;
                   minim = r[i][j2];
               }
     
     fout << minim << ' '<< i1+1 << ' ' << j1+1;
}