Cod sursa(job #553864)

Utilizator david_raucaRauca Ioan David david_rauca Data 14 martie 2011 13:06:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include<fstream>
#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,};

queue<pair<int, int> > Q;

int n, m;
char g[120][120];
int r[120][120], j1[120][120];

int ir, jr, ij, jj;

void Read();
void Solve();
void Write();

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

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

void Solve()
{
     Q.push( make_pair( ir, jr ) );
     
     r[ir][jr] = 1;
     pair<int, int> k;
     
     while( !Q.empty() )
     {
            k = Q.front();
            
            for( int d = 0; d < 8; ++d )
            {
                 int iv = k.first + di[d];
                 int jv = k.second + dj[d];
                 if( g[iv][jv] == ' ' && r[iv][jv] > r[ k.first ][ k.second ] + 1 )
                 {
                     r[iv][jv] = r[ k.first ][ k.second ] + 1;
                     Q.push( make_pair( iv, jv ) );
                 }
            }
            Q.pop();
     }
     
     Q.push( make_pair( ij, jj ) );
     
     j1[ij][jj] = 1;
     //pair<int, int> k;
     
     while( !Q.empty() )
     {
            k = Q.front();
            
            for( int d = 0; d < 8; ++d )
            {
                 int iv = k.first + di[d];
                 int jv = k.second + dj[d];
                 if( g[iv][jv] == ' ' && j1[iv][jv] > j1[ k.first ][ k.second ] + 1 )
                 {
                     j1[iv][jv] = j1[ k.first ][ k.second ] + 1;
                     Q.push( make_pair( iv, jv ) );
                 }
            }
            Q.pop();
     }
     /*
     for( int i = 0; i < n; ++i )
     {
          for( int j = 0; j < m; ++j )
               fout << r[i][j] << ' ';
          fout << '\n';
     }
     */
}

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