Cod sursa(job #2148374)

Utilizator bananamandaoneTudor Cosmin Oanea bananamandaone Data 1 martie 2018 18:10:52
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <bits/stdc++.h>
#define ValoareaMea 200000

using namespace std;

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

int n,m,xr,yr,xj,yj,r[103][103],j[1003][1003];
char a[103][103];
queue < pair<int,int> >q;
int dx[] = {1, 0,-1, 0, 1,-1,-1, 1};
int dy[] = {0, 1, 0,-1, 1, 1,-1,-1};

void Citire()
{
    int i,d;
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;++i)
        fin.getline(a[i]+1,101);
    for(i=1;i<=n;i++)
        for(d=1;d<=m;d++)
        {
            r[i][d] = j[i][d] = ValoareaMea;
            if(a[i][d] == 'R')
            {
                xr = i;
                yr = d;
            }
            else
            if(a[i][d] == 'J')
            {
                xj = i;
                yj = d;
            }
        }
}

void Bordare()
{
    int i,d;
    for(i=0;i<=n+1;i++)
        a[i][0] = a[i][m+1] = 'X';
    for(d=0;d<=m+1;d++)
        a[0][d] = a[n+1][d] = 'X';
}

void InitMat()
{
    int i,d;
    for(i=1;i<=n;i++)
        for(d=1;d<=m;d++)
            r[i][d] = j[i][d] = ValoareaMea;
}

void LeeR()
{
    int i,d,i1,j1,k;
    r[xr][yr] = 1;
    q.push({xr,yr});
    while(!q.empty())
    {
        i = q.front().first;
        d = q.front().second;
        q.pop();
        for(k=0;k<8;k++)
        {
            i1 = i + dx[k];
            j1 = d + dy[k];
            if(a[i1][j1] != 'X' && r[i1][j1] > r[i][d] + 1)
            {
                r[i1][j1] = r[i][d] + 1;
                q.push({i1,j1});
            }
        }
    }
}

void LeeJ()
{
    int i,d,i1,j1,k;
    j[xj][yj] = 1;
    q.push({xj,yj});
    while(!q.empty())
    {
        i = q.front().first;
        d = q.front().second;
        q.pop();
        for(k=0;k<8;k++)
        {
            i1 = i + dx[k];
            j1 = d + dy[k];
            if(a[i1][j1] != 'X' && j[i1][j1] > j[i][d] + 1)
            {
                j[i1][j1] = j[i][d] + 1;
                q.push({i1,j1});
            }
        }
    }
}

void Afisare()
{
    int i,d,mn,x,y;
    mn = ValoareaMea;
    for(i=1;i<=n;i++)
        for(d=1;d<=m;d++)
            if(r[i][d] == j[i][d] && r[i][d] < mn)
            {
                mn = r[i][d];
                x = i;
                y = d;
            }
    fout<<mn<<" "<<x<<" "<<y<<"\n";
}

int main()
{
    Citire();
    Bordare();
    InitMat();
    LeeR();
    LeeJ();
    Afisare();

    fin.close();
    fout.close();
    return 0;
}