Cod sursa(job #2663979)

Utilizator rusuandrei32Rusu Andrei-Cristian rusuandrei32 Data 27 octombrie 2020 18:28:13
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <queue>
#include <string>

using namespace std;

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

class Graph {
    int romeoX, romeoY, julietaX, julietaY, N, M;
    vector <vector <int>> romeo, julieta;
    vector <int> dirX, dirY;

    queue <pair <int, int>> pairs;

public:
    Graph(int N, int M) : N(N), M(M), romeo(N, vector <int> (M)), julieta(N, vector <int> (M)), dirX({-1, -1, 1, 1, -1, 0, 1, 0}), dirY({-1, 1, -1, 1, 0, -1, 0, 1}) {

        for (int i = 0; i < N; ++i) {

            string line;
            getline(in, line);

            for (int k = 0; k < M; ++k) {
                switch(line[k]) {
                    case 'X':
                        romeo[i][k] = julieta[i][k] = -1;
                        break;

                    case 'R':
                        romeoX = i;
                        romeoY = k;
                        julieta[i][k] = INT_MAX;
                        break;

                    case 'J':
                        julietaX = i;
                        julietaY = k;
                        romeo[i][k] = INT_MAX;
                        break;

                    default:
                        romeo[i][k] = julieta[i][k] = INT_MAX;
                        break;

                }
            }
        }   

        romeo[romeoX][romeoY] = 0;
        julieta[julietaX][julietaY] = 0;
    }

    bool isValid(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }

    void Lee(vector <vector <int>> &character) {
        while (pairs.size()) {
            pair <int, int> top = pairs.front();
            pairs.pop();

            for (int i = 0; i < 8; ++i) {
                int dx = dirX[i], dy = dirY[i];

                pair <int, int> neighbour = make_pair(top.first + dx, top.second + dy);

                if (!isValid(neighbour.first, neighbour.second) || character[neighbour.first][neighbour.second] == -1)    
                    continue;
                
                if (1 + character[top.first][top.second] < character[neighbour.first][neighbour.second]) {
                    character[neighbour.first][neighbour.second] = 1 + character[top.first][top.second];
                    pairs.push(neighbour);
                }

            }
        }
    }

    void solve() {
        pairs.push(make_pair(romeoX, romeoY));
        Lee(romeo);

        pairs.push(make_pair(julietaX, julietaY));
        Lee(julieta);

        int line = 0, column = 0, minDist = INT_MAX;

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j) {
                if (romeo[i][j] == julieta[i][j] && romeo[i][j] != -1 && romeo[i][j] < minDist) {
                    line = i;
                    column = j;
                    minDist = romeo[i][j];
                }
            }

        out << minDist + 1 << " " << line + 1 << " " << column + 1;
    }
};

int main() {
    int N, M;

    in >> N >> M;
    in.get();

    Graph *myGraph = new Graph(N, M);

    myGraph -> solve();

    in.close();
    out.close();

    return 0;
}