Cod sursa(job #2116350)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 27 ianuarie 2018 15:50:19
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <fstream>
#include <queue>
#define intrare "rj.in"
#define iesire "rj.out"

using namespace std;

ifstream in(intrare);
ofstream out(iesire);

struct p
{
    int x, y;
};
p romeo, julieta;

short traseu_romeo[105][105];
short traseu_julieta[105][105];
int n, m;

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

queue < pair < int , int > > coada;

bool OK(int i, int j)
{
    if(i < 1 || i > n || j < 1 || j > m)
        return false;
    return true;
}

void Read()
{
    in >> n >> m;
    in.get();
    for(int i = 1; i <= n; i++)
    {
        char c[105];
        in.getline(c, 101);
        for(unsigned j = 0; j < m; j++)
        if(c[j] == 'R')
            romeo = {i, j + 1};
        else if(c[j] == 'J')
            julieta = {i, j + 1};
        else if(c[j] == 'X')
            traseu_romeo[i][j+1] = traseu_julieta[i][j+1] = -1;
    }

}

void Lee_Romeo()
{
    traseu_romeo[romeo.x][romeo.y] = 1;
    coada.push(make_pair(romeo.x, romeo.y));
    while(!coada.empty())
    {
        int x = coada.front().first;
        int y = coada.front().second;
        coada.pop();
        for(int d = 0; d < 8; d++)
        {
            int x_new = x + dx[d];
            int y_new = y + dy[d];
            if(OK(x_new, y_new) && traseu_romeo[x_new][y_new] == 0)
            {
                traseu_romeo[x_new][y_new] = traseu_romeo[x][y] + 1;
                coada.push(make_pair(x_new, y_new));
            }
        }
    }
}

void Lee_Julieta()
{
    traseu_julieta[julieta.x][julieta.y] = 1;
    coada.push(make_pair(julieta.x, julieta.y));
    while(!coada.empty())
    {
        int x = coada.front().first;
        int y = coada.front().second;
        coada.pop();
        for(int d = 0; d < 8; d++)
        {
            int x_new = x + dx[d];
            int y_new = y + dy[d];
            if(OK(x_new, y_new) && traseu_julieta[x_new][y_new] == 0)
            {
                traseu_julieta[x_new][y_new] = traseu_julieta[x][y] + 1;
                coada.push(make_pair(x_new, y_new));
            }
        }
    }
}

void Caut_Drum()
{
    traseu_romeo[romeo.x][romeo.y] = -1;
    traseu_julieta[julieta.x][julieta.y] = -1;
    int lungime = 10000000;
    int x_lungime = 0, y_lungime = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(traseu_romeo[i][j] > 0 && traseu_julieta[i][j] > 0)
                if(traseu_romeo[i][j] == traseu_julieta[i][j])
                {
                    if(traseu_romeo[i][j] < lungime)
                        lungime = traseu_romeo[i][j], x_lungime = i, y_lungime = j;
                    else if(traseu_romeo[i][j] == lungime)
                        if(j < y_lungime)
                            lungime = traseu_romeo[i][j], x_lungime = i, y_lungime = j;
                }
        }
    out << lungime << " " << x_lungime << " " << y_lungime;
}

int main()
{
    Read();
    Lee_Romeo();
    Lee_Julieta();
    Caut_Drum();
    return 0;
}