Cod sursa(job #1925211)

Utilizator crazylamaRiclea Andrei crazylama Data 12 martie 2017 17:07:46
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.79 kb
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <cstring>
#include <utility>

using namespace std;

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

vector< list<int> > adiac;

struct cell
{
    int x, y;
};

int lines, cols, dist;
cell Romeo, Julieta;

void build_graph()
{
    in >> lines >> cols;
    char *buffer = new char[cols + 1];
    char *prev = new char[cols + 1];
    adiac.resize(lines * cols);
    int k = 0;
    for (int i = 0; i < lines; ++i)
    {
        in.getline(buffer, cols + 1);
        if (strlen(buffer) != 0)
        {
            int length = strlen(buffer);
            while (length < cols)
            {
                buffer[length] = ' ';
                ++length;
            }
            buffer[length] = '\0';
            for (int j = 0; j < cols; ++j)
            {
                if (buffer[j] == 'R')
                {
                    Romeo.x = i;
                    Romeo.y = j;
                }
                else if (buffer[j] == 'J')
                {
                    Julieta.x = i;
                    Julieta.y = j;
                }
                if (buffer[j] != 'X')
                {
                    if (i != 0)
                    {
                        if (j != 0)
                        {
                            if (prev[j - 1] != 'X')
                            {
                                adiac[k].push_back(k - cols - 1);
                                adiac[k - cols - 1].push_back(k);
                            }
                        }
                        if (j != cols - 1)
                        {
                            if (prev[j + 1] != 'X')
                            {
                                adiac[k].push_back(k - cols + 1);
                                adiac[k - cols + 1].push_back(k);
                            }
                        }
                        if (prev[j] != 'X')
                        {
                            adiac[k].push_back(k - cols);
                            adiac[k - cols].push_back(k);
                        }
                    }
                    if (j != 0)
                    {
                        if (buffer[j - 1] != 'X')
                        {
                            adiac[k].push_back(k - 1);
                            adiac[k - 1].push_back(k);
                        }
                    }
                }
                ++k;
            }
            strcpy(prev, buffer);
        }
        else
            --i;
    }
}

void write_graph()
{
    int k = 0;
    for (vector< list<int> >::iterator it = adiac.begin(); it != adiac.end(); ++it)
    {
        if ((*it).size() != 0)
        {
            out << k <<": ";
            for (list<int>::iterator jt = (*it).begin(); jt != (*it).end(); ++jt)
            {
                out << *jt << ' ';
            }
            out << '\n';
        }
        ++k;
    }
}

int BF_meet_position() {
    queue< pair<int, int> > q;
    vector<short> viz;
    vector<int> father;
    viz.resize(lines * cols, 0);
    bool ok = true;
    father.resize(lines * cols, -1);
    int start_node = (lines - 1) * Romeo.x + Romeo.y;
    father[start_node] = -2;
    int final_node = (lines - 1) * Julieta.x + Julieta.y;
    q.push(make_pair(start_node, 1));
    q.push(make_pair(final_node, 2));
    while (!q.empty())
    {
        int curr_node = q.front().first;
        int choice = q.front().second;
        viz[curr_node] = (viz[curr_node] != 0) ? viz[curr_node] : choice;
        for (list<int>::iterator it = adiac[curr_node].begin(); it != adiac[curr_node].end(); ++it)
        {
            if (viz[*it] != 0 && viz[*it] != choice)
            {
                final_node = *it;
                //father[*it] = curr_node;
                ok = false;
                break;
            }
            else if (viz[*it] != choice)
            {
                q.push(make_pair(*it, choice));
                if (choice == 1)
                    father[*it] = curr_node;
            }
        }
        q.pop();
        if (!ok)
            break;
    }
    start_node = final_node;
    dist = 0;
    do {
        ++dist;
        start_node = father[start_node];
    } while(start_node != -2 && father[start_node] != -2);
    return final_node;
}

int main()
{
    build_graph();
    int node = BF_meet_position(), k = 0;
    vector<cell> normalized_vec(lines * cols);
    for (int i = 0; i < lines; ++i)
        for (int j = 0; j < cols; ++j)
        {
            normalized_vec[k].x = i;
            normalized_vec[k++].y = j;
        }
    out << dist << " " << normalized_vec[node].x + 1 << " " << normalized_vec[node].y + 1;
    return 0;
}