Cod sursa(job #1330743)

Utilizator mariapascuMaria Pascu mariapascu Data 30 ianuarie 2015 22:12:00
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <fstream>
#include <queue>
using namespace std;

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

const int DIM = 106, INF = 0x3f3f3f3f;
const int di[] = { -1, -1, -1, 0, 1, 1, 1, 0},
          dj[] = { -1, 0, 1, 1, 1, 0, -1, -1};
int n, m, a[DIM][DIM];
int ipj, jpj, ipr, jpr;
int is, js, nrp;
char s[DIM];
int c[DIM][DIM], g[DIM][DIM];
queue<pair<int, int> > Q, Q1;
void Read();
void Julieta();
void Romeo();
bool OK(int i, int j);

int main()
{
    Read();
    Julieta();
    Romeo();
    nrp = INF;
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
            if ( c[i][j] == g[i][j] && c[i][j] != INF && nrp > c[i][j] )
            {
                nrp = c[i][j];
                is = i;
                js = j;
            }
    fout << nrp << ' ' << is << ' ' << js;
    fin.close();
    fout.close();
    return 0;
}

void Julieta()
{
    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[iv][jv] > c[i][j] + 1 )
            {
                c[iv][jv] = c[i][j] + 1;
                Q.push({iv, jv});
            }
        }
    }
}

void Romeo()
{
    int i, j, iv, jv;
    while ( !Q1.empty() )
    {
        i = Q1.front().first;
        j = Q1.front().second;
        Q1.pop();
        for ( int d = 0; d < 8; d++ )
        {
            iv = i + di[d];
            jv = j + dj[d];
            if ( OK(iv, jv) && g[iv][jv] > g[i][j] + 1 )
            {
                g[iv][jv] = g[i][j] + 1;
                Q1.push({iv, jv});
            }
        }
    }
}

bool OK(int i, int j)
{
    if ( i < 1 || i > n || j < 1 || j > m ) return false;
    if ( a[i][j] == 1 ) return false;
    return true;
}

void Read()
{
    fin >> n >> m;
    fin.get();
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
        {
            c[i][j] = INF;
            g[i][j] = INF;
        }
    for ( int i = 1; i <= n; i++ )
    {
        fin.getline(s, 106);
        for ( int j = 1; j <= m; j++ )
        {
            if ( s[j - 1] == ' ' )
                a[i][j] = 0;
            else
                if ( s[j - 1] == 'X' )
                    a[i][j] = 1;
            else
                if ( s[j - 1] == 'J' )
                {
                    a[i][j] = 0;
                    c[i][j] = 1;
                    ipj = i, jpj = j;
                    Q.push({i, j});
                }
            else
                if ( s[j - 1] == 'R' )
                {
                    a[i][j] = 0;
                    g[i][j] = 1;
                    ipr = i, jpr = j;
                    Q1.push({i, j});
                }
        }
    }
}