Cod sursa(job #2663147)

Utilizator iulia_caciucunescuIulia Caciucunescu iulia_caciucunescu Data 25 octombrie 2020 14:38:42
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

void rj()
{

    ifstream f("rj.in");
    ofstream g("rj.out");

    int n, m;

    f >> n >> m;

    //am folosit string pt distante > 9
    int** matrix = new int* [n];
    int** ro = new int* [n]; //matricea distantelor pentru Romeo
    int** ju = new int* [n]; //matricea distantelor pentru Julieta

    pair<int, int>locatieRo, locatieJu;

    for (int i = 0; i < n; i++)
    {
        matrix[i] = new int[m];
        ro[i] = new int[m];
        ju[i] = new int[m];
    }

    string s;
    getline(f, s);
    for (int i = 0; i < n; i++)
    {
        getline(f, s);
        int nr = 0;
        for (int j = 0; j < s.size(); j++)
        {
            switch (s[j])
            {
            case 'R':
                nr = -2;
                locatieRo.first = i;
                locatieRo.second = j;
                break;
            case 'J':
                nr = -3;
                locatieJu.first = i;
                locatieJu.second = j;
                break;
            case 'X':
                nr = -1;
                break;
            case ' ':
                nr = 0;
                break;
            }
            matrix[i][j] = nr;
            ro[i][j] = nr;
            ju[i][j] = nr;
        }
    }

    //acum avem matricea cu
    //R=-2; J=-3; X=-1; ' '=0

    //pornind de la r si de la j (pe rand)
    //calculam distanta pana la fiecare punct = ' '
    //ex ro[i][j]=distanta de la r la (i,j) daca ro[i][j]==' '

    //pornim de la Romeo:

    queue<pair<int, int>> q;
    q.push(locatieRo);
    while (q.size() > 0)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        pair<int, int>next;
        int currentDist = ro[x][y];
        if (currentDist == -2)
        {
            currentDist = 0;
            //daca suntem in primul pas, distanta pana la r e 0
        }
        //verificam cele 8 pozitii viitoare:
        if (x - 1 >= 0 && y - 1 >= 0)
        {
            //1
            if (ro[x - 1][y - 1] == 0)
            {
                next.first = x - 1;
                next.second = y - 1;
                q.push(next);
                ro[x - 1][y - 1] = currentDist + 1;
            }
        }
        if (x - 1 >= 0)
        {
            //2
            if (ro[x - 1][y] == 0)
            {
                next.first = x - 1;
                next.second = y;
                q.push(next);
                ro[x - 1][y] = currentDist + 1;
            }
        }
        if (x - 1 >= 0 && y + 1 < m)
        {
            //3
            if (ro[x - 1][y + 1] == 0)
            {
                next.first = x - 1;
                next.second = y + 1;
                q.push(next);
                ro[x - 1][y + 1] = currentDist + 1;
            }
        }
        if (y + 1 < m)
        {
            //4
            if (ro[x][y + 1] == 0)
            {
                next.first = x;
                next.second = y + 1;
                q.push(next);
                ro[x][y + 1] = currentDist + 1;
            }
        }
        if (x + 1 < n && y + 1 < m)
        {
            //5
            if (ro[x + 1][y + 1] == 0)
            {
                next.first = x + 1;
                next.second = y + 1;
                q.push(next);
                ro[x + 1][y + 1] = currentDist + 1;
            }
        }
        if (x + 1 < n)
        {
            //6
            if (ro[x + 1][y] == 0)
            {
                next.first = x + 1;
                next.second = y;
                q.push(next);
                ro[x + 1][y] = currentDist + 1;
            }
        }
        if (x + 1 < n && y - 1 >= 0)
        {
            //7
            if (ro[x + 1][y - 1] == 0)
            {
                next.first = x + 1;
                next.second = y - 1;
                q.push(next);
                ro[x + 1][y - 1] = currentDist + 1;
            }
        }
        if (y - 1 >= 0)
        {
            //8
            if (ro[x][y - 1] == 0)
            {
                next.first = x;
                next.second = y - 1;
                q.push(next);
                ro[x][y - 1] = currentDist + 1;
            }
        }
    }

    //acum pt Julieta:

    q.push(locatieJu);
    while (q.size() > 0)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        pair<int, int>next;
        int currentDist = ju[x][y];
        if (currentDist == -3)
        {
            currentDist = 0;
            //daca suntem in primul pas, distanta pana la r e 0
        }
        //verificam cele 8 pozitii viitoare:
        if (x - 1 >= 0 && y - 1 >= 0)
        {
            //1
            if (ju[x - 1][y - 1] == 0)
            {
                next.first = x - 1;
                next.second = y - 1;
                q.push(next);
                ju[x - 1][y - 1] = currentDist + 1;
            }
        }
        if (x - 1 >= 0)
        {
            //2
            if (ju[x - 1][y] == 0)
            {
                next.first = x - 1;
                next.second = y;
                q.push(next);
                ju[x - 1][y] = currentDist + 1;
            }
        }
        if (x - 1 >= 0 && y + 1 < m)
        {
            //3
            if (ju[x - 1][y + 1] == 0)
            {
                next.first = x - 1;
                next.second = y + 1;
                q.push(next);
                ju[x - 1][y + 1] = currentDist + 1;
            }
        }
        if (y + 1 < m)
        {
            //4
            if (ju[x][y + 1] == 0)
            {
                next.first = x;
                next.second = y + 1;
                q.push(next);
                ju[x][y + 1] = currentDist + 1;
            }
        }
        if (x + 1 < n && y + 1 < m)
        {
            //5
            if (ju[x + 1][y + 1] == 0)
            {
                next.first = x + 1;
                next.second = y + 1;
                q.push(next);
                ju[x + 1][y + 1] = currentDist + 1;
            }
        }
        if (x + 1 < n)
        {
            //6
            if (ju[x + 1][y] == 0)
            {
                next.first = x + 1;
                next.second = y;
                q.push(next);
                ju[x + 1][y] = currentDist + 1;
            }
        }
        if (x + 1 < n && y - 1 >= 0)
        {
            //7
            if (ju[x + 1][y - 1] == 0)
            {
                next.first = x + 1;
                next.second = y - 1;
                q.push(next);
                ju[x + 1][y - 1] = currentDist + 1;
            }
        }
        if (y - 1 >= 0)
        {
            //8
            if (ju[x][y - 1] == 0)
            {
                next.first = x;
                next.second = y - 1;
                q.push(next);
                ju[x][y - 1] = currentDist + 1;
            }
        }
    }

    pair<int, int> best;
    int distMin = max(n, m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (ro[i][j] == ju[i][j] && ju[i][j] > 0 && ro[i][j] < distMin)
            {
                distMin = ro[i][j];
                best.first = i;
                best.second = j;
            }
        }
    }

    g << distMin + 1 << " " << best.first + 1 << " " << best.second + 1;
}

int main()
{
    rj();
    return 0;
}