Cod sursa(job #1124478)

Utilizator fetti_danutzdezactivat fetti_danutz Data 26 februarie 2014 12:29:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <queue>
using namespace std;

ifstream fin ("rj.in");
ofstream fout ("rj.out");
const int INF = 0x3f3f3f3f;
const int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          dj[8] = { 0,  1, 1, 1, 0,-1,-1, -1};
int m, n, iM, jM;
int a[102][102];
int b[102][102];
char t[102][102], x;

struct Cel{
    int i, j;
} R, J;

queue<pair<int, int> > Q;

void Read();
void LeeR();
void LeeJ();
bool Ok(int i, int j);

void Solve();

int main()
{
    Read();
    LeeR();
    LeeJ();
    Solve();
    return 0;
}

void Solve()
{
    int mi = INF;
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
        {
            if (a[i][j] == b[i][j] && a[i][j] != 0 && a[i][j] < mi)
                iM = i, jM = j, mi = a[i][j];
        }
    fout << mi << ' ' << iM << ' ' << jM;
}

void LeeJ()
{
    int i, j, iv, jv;
    b[J.i][J.j] = 1;
    Q.push(make_pair(J.i, J.j));
    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) && b[iv][jv] < 1 )
                b[iv][jv] = b[i][j] + 1, Q.push(make_pair(iv, jv));
        }
    }
}

void LeeR()
{
    int i, j, iv, jv;
    a[R.i][R.j] = 1;
    Q.push(make_pair(R.i, R.j));
    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) && a[iv][jv] < 1 )
                a[iv][jv] = a[i][j] + 1, Q.push(make_pair(iv, jv));
        }
    }
}

bool Ok(int i, int j)
{
    if (i < 1 || j < 1 || i > n || j > m)
        return false;
    if (t[i][j] == 'X')
        return false;
    return true;
}

void Read()
{
    fin >> n >> m;
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
        {
            x = fin.get();
            if (x == '\n') x = fin.get();
            if (x == 'X' || x == 'R' || x == 'J' || x == ' ')
                t[i][j] = x;
            if (x == 'R') R.i = i, R.j = j;
            if (x == 'J') J.i = i, J.j = j;
        }
}