Cod sursa(job #2681485)

Utilizator costi13Costi Tica costi13 Data 5 decembrie 2020 17:45:00
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.25 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <cstring>
#include <unordered_set>


using namespace std;

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

void print(int n, int m, vector<vector<int>>& adj, int romeo, int julieta){
    for(int i = 0; i < n * m; ++i){
        cout << i << ": ";
        for (unsigned int j = 0; j < adj[i].size(); ++j){
            cout << adj[i][j] << " ";
        }
        cout << '\n';
    }
    cout << endl;

    cout << "Romeo: " << romeo << "\nJulieta: " << julieta << '\n';
}

void insert_edges(int n, int m, int i, int j, vector<vector<int>>& adj, const unordered_set<int>& valid_points){
    int v_up = m*(i - 1) + j;
    int v_diag_left = m*(i - 1) + (j - 1);
    int v_diag_right = m*(i - 1) + (j + 1);
    int v_left = m*i + (j - 1);

    if (v_up >= 0 && valid_points.find(v_up) != valid_points.end()){
        adj[m*i + j].push_back(v_up);
        adj[v_up].push_back(m*i + j);
    }
    if (i != 0 && j != 0 && valid_points.find(v_diag_left) != valid_points.end()){
        adj[m*i + j].push_back(v_diag_left);
        adj[v_diag_left].push_back(m*i + j);
    }
    if (i != 0 && j != m - 1 && valid_points.find(v_diag_right) != valid_points.end()){
        adj[m*i + j].push_back(v_diag_right);
        adj[v_diag_right].push_back(m*i + j);
    }
    if (v_left % m != m - 1 && v_left >= 0 && valid_points.find(v_left) != valid_points.end()){
        adj[m*i + j].push_back(v_left);
        adj[v_left].push_back(m*i + j);
    }
}

void read(int& n, int& m, vector<vector<int>>& adj, int& romeo,  int& julieta){
    unordered_set<int> valid_points;

    fin >> n >> m;

    for(int i = 0; i < n * m; ++i){
        vector<int> v;
        adj.push_back(v);
    }

    char x[m+1];
    fin.getline(x, m+1);
    for(int i = 0; i < n; ++i){
        fin.getline(x, m+1);

        int length = strlen(x);
        for (int j = 0; j < length; ++j){
            if (x[j] == 'R'){
                romeo = m*i + j;
            } else if (x[j] == 'J'){
                julieta = m*i + j;
            }
            if (x[j] == 'R' || x[j] == 'J' || x[j] == ' '){
                valid_points.insert(m*i +j);
                insert_edges(n, m, i, j, adj, valid_points);

            }
        }
        while (length < m){
            valid_points.insert(m*i + length);
            insert_edges(n, m, i, length, adj, valid_points);
            ++length;
        }
    }
}

void BFS(queue<int>& q, vector<vector<int>>& adj, vector<bool>& visited, int julieta, vector<int>& parent, vector<int>& level){
    while (!q.empty()){
        int u = q.front();
        q.pop();

        for (unsigned int i = 0; i < adj[u].size(); ++i){
            int v = adj[u][i];

            if (!visited[v]){
                parent[v] = u;
                visited[v] = true;
                level[v] = level[u] + 1;

                if (v == julieta && level[v]%2 == 0)
                    return;
                else if (v == julieta){
                    parent[v] = -1;
                    visited[v] = false;
                    level[v] = 0;
                } else
                    q.push(v);
            }
        }
    }
}

int solve(int n, vector<vector<int>>& adj, int romeo, int julieta, vector<int>& parent){
    queue<int> q;
    vector<bool> visited(n, false);
    vector<int> level(n, 0);
    for (int i = 0; i < n; ++i){
        parent.push_back(-1);
    }

    q.push(romeo);
    visited[romeo] = true;

    BFS(q, adj, visited, julieta, parent, level);

    return level[julieta];
}

void print_solution(int m, int julieta, int distance, vector<int>& parent){
    //cout << distance;
    int middle_point = distance/2;
    while (distance != middle_point){
        julieta = parent[julieta];
        --distance;
    }
    fout << middle_point + 1 << ' ' << julieta / m + 1 << ' ' << julieta % m + 1;
}

int main()
{
    int n, m;
    vector<vector<int>> adj;
    vector<int> parent;
    int romeo, julieta;
    int distance;

    read(n, m, adj, romeo, julieta);
    //print(n, m, adj, romeo, julieta);

    distance = solve(n * m, adj, romeo, julieta, parent);
    print_solution(m, julieta, distance, parent);

    return 0;
}