Cod sursa(job #2183484)

Utilizator vladut_programatorVladutz vladut_programator Data 23 martie 2018 10:44:03
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.22 kb
#include <cstdio>
#include <queue>
#include <climits>

using namespace std;

const int INF_INT = INT_MAX;
const char INF_CHAR = SCHAR_MAX;

struct coord
{
    int i, j;
    bool operator!= (const coord& dp)
    {
        if (i != dp.i || j != dp.j)
            return true;
        return false;
    }
    bool operator== (coord& dp)
    {
        if (i == dp.i && j == dp.j)
            return true;
        return false;
    }
    bool is_neighbour (coord& dp)
    {
        if (i == INF_INT || j == INF_INT)
            return false;
        coord temp;

        coord NO_NEIGH = {INF_INT, INF_INT};
        extern coord (get_neighbour) (const coord&);

        while ((temp = _get_neighbour()) != NO_NEIGH)
            if (temp == dp)
             return true;
        return false;
    }

    coord _get_neighbour()
    {
        static int vis_neighbours = 0;

        if (vis_neighbours == 8)
        {
            vis_neighbours = 0;
            return {INF_INT, INF_INT};
        }

        extern bool e_valid(int, int);

        vis_neighbours++;
        switch(vis_neighbours)
        {
            case 1: if (e_valid(i + 1, j - 1)) return {i + 1, j - 1}; else return {-1, -1};
            case 2: if (e_valid(i, j - 1)) return {i, j - 1}; else return {-1, -1};
            case 3: if (e_valid(i - 1, j - 1)) return {i - 1, j - 1}; else return {-1, -1};
            case 4: if (e_valid(i + 1, j)) return {i + 1, j}; else return {-1, -1};
            case 5: if (e_valid(i - 1, j)) return {i - 1, j}; else return {-1, -1};
            case 6: if (e_valid(i + 1, j + 1)) return {i + 1, j + 1}; else return {-1, -1};
            case 7: if (e_valid(i, j + 1)) return {i, j + 1}; else return {-1, -1};
            case 8: if (e_valid(i - 1, j + 1)) return {i - 1, j + 1};
            default: vis_neighbours = 0; return {INF_INT, INF_INT};
        }
    }
}R, J;

const coord NO_NEIGH = {INF_INT, INF_INT}, NOT_YET = {-1, -1};

int nr_col, nr_linii;
char **m_city;

bool e_valid (int i, int j)
{
    if (i < 0 || i >= nr_linii || j < 0 || j >= nr_col || m_city[i][j] == 0)
        return 0;
    return 1;
}

coord get_neighbour(const coord& curr)
{
    static int vis_neighbours = 0;

    if (vis_neighbours == 8)
    {
        vis_neighbours = 0;
        return NO_NEIGH;
    }

    vis_neighbours++;
    switch(vis_neighbours)
    {
        case 1: if (e_valid(curr.i + 1, curr.j - 1)) return {curr.i + 1, curr.j - 1}; else return NOT_YET;
        case 2: if (e_valid(curr.i, curr.j - 1)) return {curr.i, curr.j - 1}; else return NOT_YET;
        case 3: if (e_valid(curr.i - 1, curr.j - 1)) return {curr.i - 1, curr.j - 1}; else return NOT_YET;
        case 4: if (e_valid(curr.i + 1, curr.j)) return {curr.i + 1, curr.j}; else return NOT_YET;
        case 5: if (e_valid(curr.i - 1, curr.j)) return {curr.i - 1, curr.j}; else return NOT_YET;
        case 6: if (e_valid(curr.i + 1, curr.j + 1)) return {curr.i + 1, curr.j + 1}; else return NOT_YET;
        case 7: if (e_valid(curr.i, curr.j + 1)) return {curr.i, curr.j + 1}; else return NOT_YET;
        case 8: if (e_valid(curr.i - 1, curr.j + 1)) return {curr.i - 1, curr.j + 1};
        default: vis_neighbours = 0; return NO_NEIGH;
    }
}


void citesc_date(const char* t)
{
    FILE *f = fopen(t, "r");

    fscanf(f, "%d %d", &nr_linii, &nr_col);

    m_city = new char*[nr_linii];

    for (int i = 0; i < nr_linii; i++)
        m_city[i] = new char[nr_col];
    fscanf(f, "%*c");
    char c[101];
    for (int i = 0; i < nr_linii; i++)
    {
        fgets(c, 102, f);
        for (int j = 0; j < nr_col; j++)
        {
            if (c[j] == 'R')
            {
                m_city[i][j] = 1;
                R.i = i;
                R.j = j;
            }
            else if (c[j] == 'J')
            {
                m_city[i][j] = 1;
                J.i = i;
                J.j = j;
            }
            else if (c[j] == ' ')
                m_city[i][j] = 1;
            else if (c[j] == 'X')
                m_city[i][j] = 0;
        }
    }

    fclose(f);
}

void BFS(char ** &m_dist, coord ** &m_parrent)
{
    queue <coord> Q;

    m_dist = new char* [nr_linii];
    m_parrent = new coord* [nr_linii];

    for (int i = 0; i < nr_linii; i++)
    {
        m_dist[i] = new char [nr_col];
        m_parrent[i] = new coord [nr_col];

        for (int j = 0; j < nr_col; j++)
            m_dist[i][j] = INF_CHAR;
    }

    m_dist[R.i][R.j] = 0;
    m_parrent[R.i][R.j] = {-1, -1};

    Q.push(R);

    coord curr, neigh;

    while (!Q.empty())
    {
        curr = Q.front();
        Q.pop();
        if (curr == J)
            break;

        while ((neigh = get_neighbour(curr)) != NO_NEIGH)
            if (neigh != NOT_YET && m_dist[neigh.i][neigh.j] == INF_CHAR)
            {
                m_dist[neigh.i][neigh.j] = m_dist[curr.i][curr.j] + 1;
                m_parrent[neigh.i][neigh.j] = curr;
                Q.push(neigh);
            }
    }
}

struct solution
{
    coord x;
    int d;
};

solution solve()
{
    char **m_dist;
    coord **m_parrent;
    BFS(m_dist, m_parrent);

    int d = m_dist[J.i][J.j];
    coord curr = J, upper_middle, lower_middle;

    while ((d / 2 + 1) != m_dist[curr.i][curr.j])
        curr = m_parrent[curr.i][curr.j];

    upper_middle = curr; lower_middle = m_parrent[curr.i][curr.j];

    if (d % 2 == 0)
        return {{lower_middle.i + 1, lower_middle.j + 1}, d / 2 + 1};

    while ((curr = get_neighbour(lower_middle)) != NO_NEIGH)
        if (curr != NOT_YET && curr != upper_middle && curr.is_neighbour(upper_middle))
            break;

    if (lower_middle.j < curr.j)
    {
        coord prev = lower_middle, next = m_parrent[lower_middle.i][lower_middle.j], stop = {-1, -1};

        while (next != stop)
        {
            coord neigh;
            while ((neigh = get_neighbour(next)) != NO_NEIGH)
                if (neigh != NOT_YET && neigh != prev && neigh.is_neighbour(prev))
                {
                    curr = lower_middle; goto eticheta1;
                }
            prev = next;
            next = m_parrent[next.i][next.j];
        }
    }

    eticheta1:

    if (upper_middle.j < curr.j)
    {
        coord prev = J, next = m_parrent[J.i][J.j];

        while (next != lower_middle)
        {
            coord neigh;
            while ((neigh = get_neighbour(next)) != NO_NEIGH)
                if (neigh != NOT_YET && neigh != prev && neigh.is_neighbour(prev))
                {
                    curr = upper_middle; goto eticheta2;
                }
            prev = next;
            next = m_parrent[next.i][next.j];
        }
    }

    eticheta2:


    for (int i = 0; i < nr_linii; i++)
    {
        delete [] m_dist[i];
        delete [] m_parrent[i];
    }
    delete [] m_dist;
    delete [] m_parrent;

    return {{curr.i + 1, curr.j + 1}, d / 2 + 2};
}


int main()
{
    citesc_date("rj.in");

    solution S = solve();

    FILE *f = fopen("rj.out", "w");
    fprintf(f, "%d %d %d", S.d, S.x.i, S.x.j);

    for (int i = 0; i < nr_linii; i++)
        delete [] m_city[i];
    delete [] m_city;

    fclose(f);
}