Cod sursa(job #2146360)

Utilizator ArsuhArsene Vlad Arsuh Data 27 februarie 2018 22:31:58
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <fstream>
#include <queue>
#include <cstring>
#include <climits>

using namespace std;

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

int a[101][101], b[101][101], n, m;

struct romjul
{
    int x, y;
} rom,jul;

void citire()
{
    f>>n>>m;
    f.get();
    char aux[101];
    for(int i=1; i<=n; i++)
    {
        f.getline(aux,101);
        for(int j=0; j<strlen(aux); j++)
            if(aux[j]=='X')
            {
                a[i][j+1]=-1;
                b[i][j+1]=-1;
            }
            else if(aux[j]=='J')
            {
                a[i][j+1]=1;
                rom.x=i;
                rom.y=j+1;
            }
            else if(aux[j]=='R')
            {
                b[i][j+1]=1;
                jul.x=i;
                jul.y=j+1;
            }
    }
}

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

queue <pair<int, int > >q,q2;
int di[]= {1,-1,0,0};
int dj[]= {0,0,1,-1};

void LeeR ()
{
    int i, j, i2, j2;
    q.push(make_pair(rom.x,rom.y));

    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();

        for(int dir=0; dir<4; dir++)
        {
            i2=i+di[dir];
            j2=j+dj[dir];
            if(ok(i2,j2) && a[i2][j2]<1)
            {
                a[i2][j2]=a[i][j]+1;
                q.push(make_pair(i2,j2));
            }
        }
    }
}

void LeeJ ()
{
    int i, j, i2, j2;
    q2.push(make_pair(jul.x,jul.y));

    while(!q2.empty())
    {
        i=q2.front().first;
        j=q2.front().second;
        q2.pop();

        for(int dir=0; dir<4; dir++)
        {
            i2=i+di[dir];
            j2=j+dj[dir];
            if(ok(i2,j2) && b[i2][j2]<1)
            {
                b[i2][j2]=b[i][j]+1;
                q2.push(make_pair(i2,j2));
            }
        }
    }
}

void cmp(int &x, int &y)
{
    int mini=INT_MAX;
    for(int i=1; i<n; i++)
        for(int j=1; j<m; j++)
        {
            if(a[i][j]==b[i][j] && a[i][j]!=-1 && a[i][j]<mini)
            {
                mini=a[i][j];
                x=i;
                y=j;
            }
        }
}

int main()
{
    citire();
    LeeR();
    LeeJ();
    int x, y;
    cmp(x,y);
    g<<x<<' '<<y<<' '<<a[x][y]-1;

    return 0;
}