Cod sursa(job #1322005)

Utilizator IonutNicolaeRaIonut Raucea IonutNicolaeRa Data 19 ianuarie 2015 18:41:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
#define Dim 160
#define INF 0x3f3f3f3f
const int di[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
const int dj[] = { -1,  0,  1, 1, 1, 0,-1,-1 };
queue<pair<int,int> >Q, Q1;
int n, m, ipoz = INF, jpoz = INF;
char s[165];
int c[Dim][Dim];
int a[Dim][Dim];
int d[Dim][Dim];
void Read();
void LeeRomeo();
void LeeJuli();
bool Ok(int i, int j);
int minim = INF, imin, jmin;
int main()
{
    Read();
    LeeRomeo();
    LeeJuli();
    for ( int i = 0; i < n; ++i )
        for ( int j = 0; j < m; ++j )
            if ( c[i][j] == d[i][j] && c[i][j] && a[i][j] == 1 )
                if ( c[i][j] < minim )
                {
                    minim = c[i][j];
                    imin = i + 1;
                    jmin = j + 1;
                }
    fout << minim << ' ' << imin << ' ' << jmin;
    fin.close();
    fout.close();
    return 0;
}
void LeeJuli()
{
    int i, j, iv, jv;
    while ( !Q1.empty() )
    {
        i = Q1.front().first;
        j = Q1.front().second;
        Q1.pop();
        for ( int p = 0; p < 8; ++p )
        {
            iv = i + di[p];
            jv = j + dj[p];
            if ( Ok( iv, jv ) && d[i][j] + 1 < d[iv][jv] )
            {
                d[iv][jv] = d[i][j] + 1;
                Q1.push( { iv, jv });
            }
        }
    }
}
void LeeRomeo()
{
    int i, j, iv, jv;
    while ( !Q.empty() )
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for ( int d = 0; d < 8; ++d )
        {
            iv = i + di[d];
            jv = j + dj[d];
            if ( Ok( iv, jv ) && c[i][j] + 1 < c[iv][jv] )
            {
                c[iv][jv] = c[i][j] + 1;
                Q.push( { iv, jv });
            }
        }
    }
}
bool Ok(int i, int j)
{
    if ( i < 0 or i > n - 1 or j < 0 or j > m - 1 or a[i][j] == -1 )
        return false;
    return true;
}
void Read()
{
    fin >> n >> m;
    fin.get();
    for ( int i = 0; i < n; ++i )
    {
        fin.getline( s, 150, '\n' );
        for ( int j = 0; j < m; ++j )
        {
            if ( s[j] == ' ' )
                a[i][j] = 1;
            if ( s[j] == 'X' )
                a[i][j] = -1;
            c[i][j] = d[i][j] = INF;
            if ( s[j] == 'R')
            {
                Q.push( {i, j});
                c[i][j] = 1;
            }
            if ( s[j] == 'J' )
            {
                Q1.push( {i, j});
                d[i][j] = 1;
            }
        }
    }
}