Cod sursa(job #1317234)

Utilizator blackoddAxinie Razvan blackodd Data 14 ianuarie 2015 19:01:54
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 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;
            }
        }
    }
}