Cod sursa(job #2663120)

Utilizator CosminPetrescuPetrescu Cosmin CosminPetrescu Data 25 octombrie 2020 13:40:57
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.17 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] && ro[i][j] > 0) {
                if (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;
}