Cod sursa(job #1130851)

Utilizator XeBluePodaru Mihai XeBlue Data 28 februarie 2014 16:02:12
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <fstream>
#include <queue>

using namespace std;

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

#define N 105

const int dlin[]= {-1, -1, -1, 0, 1, 1, 1, 0};
const int dcol[]= {-1, 0, 1, 1, 1, 0, -1, -1};

struct poz{
    int linie, coloana;
};

queue <poz> q;

int a[N][N], n, m, rl, rc, jl, jc, b[N][N];
char v[N];

void citire();
void bordare();
void lee();

int main()
{
    citire();
    bordare();
    lee();

    in.close();
    out.close();
    return 0;
}

void citire()
{
    in >> n >> m >> ws;
    for(int i=1;i<=n;i++)
    {
        in.getline(v, N);
        for(int j=0;j<m;j++)
        {
            if(v[j]=='X')
            {
                a[i][j+1]=-1;
                b[i][j+1]=-1;
            }
            if(v[j]=='R')
            {
                rl=i;
                rc=j+1;
                a[i][j+1]=1;
            }
            if(v[j]=='J')
            {
                jl=i;
                jc=j+1;
                b[i][j+1]=1;
            }
        }
    }
}

void bordare()
{
    for(int i=0;i<=m+1;i++)
    {
        a[0][i]=-1;
        b[0][i]=-1;
        a[n+1][i]=-1;
        b[n+1][i]=-1;
    }
    for(int i=0;i<=n+1;i++)
    {
        a[i][0]=-1;
        b[i][0]=-1;
        a[i][m+1]=-1;
        b[i][m+1]=-1;
    }
}

void lee()
{
    poz x, y;
    x.linie=rl;
    x.coloana=rc;
    q.push(x);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(int i=0;i<=7;i++)
        {
            y.linie=x.linie + dlin[i];
            y.coloana=x.coloana + dcol[i];
            if(a[y.linie][y.coloana]==0)
            {
                a[y.linie][y.coloana]=1+a[x.linie][x.coloana];
                q.push(y);
            }
        }
    }
    x.linie=jl;
    x.coloana=jc;
    q.push(x);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(int i=0;i<=7;i++)
        {
            y.linie=x.linie + dlin[i];
            y.coloana=x.coloana + dcol[i];
            if(b[y.linie][y.coloana]==0)
            {
                b[y.linie][y.coloana]=1+b[x.linie][x.coloana];
                q.push(y);
                if(a[y.linie][y.coloana]==b[y.linie][y.coloana])
                {
                    out << b[y.linie][y.coloana] << " " << y.linie << " " << y.coloana;
                    return;
                }
            }
        }
    }
}