Cod sursa(job #1376839)

Utilizator bilbor987Bogdan Pocol bilbor987 Data 5 martie 2015 19:04:25
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 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> > coada;

void Solve()
{
    int mi = INF;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {//Cross the matrix
            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;
}

bool Ok(int i, int j)
{
    if (i < 1 || j < 1 || i > n || j > m) //If pass the margins
        return false;
    if (t[i][j] == 'X') //If is an obstacle
        return false;
    return true; //Else is ok
}

void LeeJ()
{
    int i, j, iv, jv;
    b[J.i][J.j] = 1;
    coada.push(make_pair(J.i, J.j)); //Insert the Juliet's coordinates
    while ( !coada.empty() ) //If there are elements in queue
    {
        i = coada.front().first; //Extract first element from queue
        j = coada.front().second; //Extract second element from queue
        coada.pop(); //Remove the oldest element from queue
        for (int d = 0; d < 8; d++)
        {
            iv = i + di[d]; //Put the coordinates
            jv = j + dj[d]; //Put the coordinates
            if (Ok(iv, jv) && b[iv][jv] < 1)
            {//If it's ok and the new b is 0 :)
                b[iv][jv] = b[i][j] + 1;
                coada.push(make_pair(iv, jv));
            }
        }
    }
}

void LeeR()
{
    int i, j, iv, jv;
    a[R.i][R.j] = 1;
    coada.push(make_pair(R.i, R.j)); //Insert the Romeo's coordinates
    while (!coada.empty()) //If there are elements in queue
    {
        i = coada.front().first; //Extract first element from queue
        j = coada.front().second; //Extract second element from queue
        coada.pop(); //Remove the oldest element from queue
        for (int d = 0; d < 8; d++)
        {
            iv = i + di[d]; //Put the coordinates
            jv = j + dj[d]; //Put the coordinates
            if ( Ok(iv, jv) && a[iv][jv] < 1 )
            {//If it's ok and the new a is 0 :)
                a[iv][jv] = a[i][j] + 1;
                coada.push(make_pair(iv, jv));
            }
        }
    }
}

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;
        }
    }
}

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