Cod sursa(job #2714709)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 2 martie 2021 12:39:26
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>

#define int long long

using namespace std;

ifstream fin("rj.in");

ofstream fout("rj.out");

int romeo[105][105];
int julieta[105][105];
int v[105][105];
char c[105];
int n, m;
int di[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dj[8] = {0, 0, -1, 1, 1, -1, -1, 1};
int RLin, RCol, JLin, JCol;

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

queue<pair<int,int>> coada;

void R(int lin, int col)
{
    coada.push(make_pair(lin,col));
    while(!coada.empty())
    {
        int l = coada.front().first;
        int c = coada.front().second;
        coada.pop();
        for(int i = 0; i < 8; i ++)
        {
            int lnou = l + di[i];
            int cnou = c + dj[i];
            if(verifica(lnou,cnou) && romeo[l][c] + 1 < romeo[lnou][cnou])
            {
                romeo[lnou][cnou] = romeo[l][c] + 1;
                coada.push(make_pair(lnou,cnou));
            }
        }
    }
}

void J(int lin, int col)
{
    coada.push(make_pair(lin,col));
    while(!coada.empty())
    {
        int l = coada.front().first;
        int c = coada.front().second;
        coada.pop();
        for(int i = 0; i < 8; i ++)
        {
            int lnou = l + di[i];
            int cnou = c + dj[i];
            if(verifica(lnou,cnou) && julieta[l][c] + 1 < julieta[lnou][cnou])
            {
                julieta[lnou][cnou] = julieta[l][c] + 1;
                coada.push(make_pair(lnou,cnou));
            }
        }
    }
}


int32_t main()
{
    fin >> n >> m;

    fin.get();

    for(int i = 1; i <= n; i ++)
    {
        fin.getline(c,108);
        for(int j = 0; j < m; j ++)
        {
            romeo[i][j+1] = INT_MAX;
            julieta[i][j+1] = INT_MAX;
            if(c[j] == 'X')
                v[i][j+1] = -1;
            if(c[j] == 'R')
            {
                romeo[i][j+1] = 1;
                RLin = i;
                RCol = j+1;
            }
            if(c[j] == 'J')
            {
                julieta[i][j+1] = 1;
                JLin = i;
                JCol = j+1;
            }
        }
    }
    R(RLin,RCol);
    J(JLin,JCol);

    int minim = INT_MAX, lin = 0, col = 0;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(v[i][j] != -1 && romeo[i][j] == julieta[i][j] && romeo[i][j] < minim)
            {
                minim = romeo[i][j];
                lin = i;
                col = j;
            }
        }
    }
    fout << minim << ' ' << lin << ' ' << col << '\n';
    return 0;
}