Cod sursa(job #2491164)

Utilizator andreigaliAndrei Galitianu andreigali Data 11 noiembrie 2019 22:19:15
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <queue>

using namespace std;

int n, m;
char a[110][100];
int mapa[110][100];

struct coord
{
    int n, m;
    ///  n, i      m, j
};

coord make_pare(int x, int y)
{
    coord aux;
    aux.n = x;
    aux.m = y;
    return aux;
}

int main()
{
    short int di[8]= {-1,  0,  1, -1, 1, -1, 0, 1};
    short int dj[8]= {-1, -1, -1,  0, 0,  1, 1, 1};

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

    fin >> n >> m;
    fin.getline(a[0], 100);
    for(int i=0; i<n; i++)
        fin.getline(a[i], 100);

    queue<coord> qr, qj;


    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(a[i][j] == 'R')
            {
                mapa[i][j] = 1;
                qr.push(make_pare(i, j));
            }
            if(a[i][j] == 'J')
            {
                mapa[i][j] = 1;
                qj.push(make_pare(i, j));
            }
            if(a[i][j] == 'X')
                mapa[i][j] = -1;
        }
    }

    while(!qr.empty() || !qj.empty())
    {
        int i=qr.front().n;
        int j=qr.front().m;
        qr.pop();
        int k=mapa[i][j];///retzin in k numarul pasului curent
        ///vad unde se poate sari de la (i,j) shi e neocupat
        for(int l=0; l<=7; l++)
        {
            if(mapa[i+di[l]][j+dj[l]] == (k+1) )
            {
                fout << k+1 << " " << i+di[l]+1 << " " << j+dj[l]+1;
                return 0;
            }

            if(0<=i+di[l] && i+di[l]<n && 0<=j+dj[l] && j+dj[l]<m &&
                    mapa[i+di[l]][j+dj[l]]==0)
            {
                qr.push(make_pare(i+di[l],j+dj[l]));
                mapa[i+di[l]][j+dj[l]]=k+1;
            }
        }

        i=qj.front().n;
        j=qj.front().m;
        qj.pop();
        k=mapa[i][j];///retzin in k numarul pasului curent
        ///vad unde se poate sari de la (i,j) shi e neocupat
        for(int l=0; l<=7; l++)
            if(0<=i+di[l] && i+di[l]<n && 0<=j+dj[l] && j+dj[l]<m &&
                    (mapa[i+di[l]][j+dj[l]]==0 || mapa[i+di[l]][j+dj[l]]==k+1))
            {
                qj.push(make_pare(i+di[l],j+dj[l]));
                mapa[i+di[l]][j+dj[l]]=k+1;
            }
    }

    return 0;
}