Cod sursa(job #2182267)

Utilizator Dragos123Tatar Dragos Vlad Dragos123 Data 22 martie 2018 11:50:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <iostream>
#include <tuple>
#include <queue>

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

const int MaxN = 101, Inf = 1 << 30;
int n, m, t1[MaxN][MaxN], t2[MaxN][MaxN], minim;
int ir, jr, ij, jj, is, js;
char a[MaxN][MaxN];
const int di[] = {-1,-1,-1, 0, 1, 1, 1, 0},
          dj[] = {-1, 0, 1, 1, 1, 0,-1,-1};

void ReadData();
bool Ok(int i, int j);
void Lee(int ip, int jp, int t[MaxN][MaxN]);
void Solve();
void Write();

int main ()
{
    ReadData();
    Solve();
    Write();

    fin.close();
    fout.close();

    return 0;
}

void ReadData()
{
    fin >> n >> m;

    fin.get();

    for (int i = 1; i <= n; ++i)
        fin.getline(a[i] + 1, MaxN);
}

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

void Lee(int ip, int jp, int t[MaxN][MaxN])
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            t[i][j] = Inf;

    std::queue<std::pair<int, int>> Q;

    Q.push( {ip, jp} );

    t[ip][jp] = 1;

    int i, j;
    int iv, jv;

    while (!Q.empty())
    {
        std::tie(i, j) = Q.front();

        for (int k = 0; k < 8; ++k)
        {
            iv = i + di[k];
            jv = j + dj[k];

            if (Ok(iv, jv) && t[iv][jv] > t[i][j] + 1)
            {
                t[iv][jv] = t[i][j] + 1;
                Q.push( {iv, jv} );
            }
        }

        Q.pop();
    }
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == 'R')
            {
                ir = i;
                jr = j;
            }

            if (a[i][j] == 'J')
            {
                ij = i;
                jj = j;
            }
        }

    Lee(ir, jr, t1);
    Lee(ij, jj, t2);

    minim = Inf;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if(t1[i][j] == t2[i][j])
            {
                if (minim > t1[i][j])
                {
                    minim = t1[i][j];
                    is = i;
                    js = j;
                }
            }
}

void Write()
{
    fout << is << ' ' << js << ' ' << minim;
}