Cod sursa(job #2604389)

Utilizator amalia.gemanGeman Aamalia amalia.geman Data 22 aprilie 2020 16:08:08
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <queue>
#define N 110
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

int n, m;
int R[N][N], lr, cr; ///matrice care retine lungimile distantelor parcurse de Romeo
int J[N][N], lj, cj; ///matrice care retine lungimile distantelor parcurse de Julieta
int dl[]= {-1,0,1,0,-1,1,1,-1};
int dc[]= {0,1,0,-1,1,1,-1,-1};

void Read()
{
    int i, j;
    char s[101];

    fin >> n >> m;
    fin.get();

    for(int i=1; i<=n; i++)
    {
        fin.getline(s,101);
        for(j=0; s[j]; j++)
            if(s[j] == ' ')
                R[i][j+1] = J[i][j+1] = 0;
            else
                if(s[j] == 'R')
                    lr=i, cr=j+1, R[i][j+1] = J[i][j+1] = 0;
            else
                if(s[j] == 'J')
                    lj=i, cj=j+1, R[i][j+1] = J[i][j+1] = 0;
            else
                R[i][j+1] = J[i][j+1] = -1;
    }
}

void Bordare()
{
    for(int j=0; j<=m+1; j++)
        R[0][j] = R[n+1][j] = J[0][j] = J[n+1][j] = -1;
    for(int i=0; i<=n+1; i++)
        R[i][0] = R[i][m+1] = J[i][0] = J[i][m+1] = -1;
}

void LeeR()
{
    int l, c, lv, cv, k;
    queue <int> L, C;
    L.push(lr);
    C.push(cr);

    while(!L.empty())
    {
        l = L.front();
        L.pop();
        c = C.front();
        C.pop();
        for(k=0; k<8; k++)
        {
            lv = dl[k] + l;
            cv = dc[k] + c;
            if(R[lv][cv] == 0)
                {
                    R[lv][cv] = R[l][c] + 1;
                    L.push(lv);
                    C.push(cv);
                }
        }
    }
}

void LeeJ()
{
    int l, c, lv, cv, k;
    queue <int> L, C;
    L.push(lj);
    C.push(cj);

    while(!L.empty())
    {
        l = L.front();
        L.pop();
        c = C.front();
        C.pop();
        for(k=0; k<8; k++)
        {
            lv = dl[k] + l;
            cv = dc[k] + c;
            if(J[lv][cv] == 0)
            {
                J[lv][cv] = J[l][c] + 1;
                L.push(lv);
                C.push(cv);
            }
        }
    }
}

void Solve()
{
    int lmin, cmin, mini = 20000;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(R[i][j] == J[i][j] && R[i][j] != -1 && R[i][j] != 0)
                if(R[i][j] < mini)
                {
                    lmin = i;
                    cmin = j;
                    mini = R[i][j];
                }
    fout << mini+1 <<" ";
    fout << lmin << " " << cmin;
}

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

/*
for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            fout << R[i][j] << " ";
    fout << "\n";
    }
*/