Cod sursa(job #2183643)

Utilizator vladut_programatorVladutz vladut_programator Data 23 martie 2018 12:17:43
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.81 kb
#include <cstdio>
#include <queue>
#include <climits>

using namespace std;

const int INF_INT = INT_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;
    }
}R, J;

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

int nr_col, nr_linii;
int m_j[101][101], m_r[101][101];;

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

inline coord get_neighbour(const coord& curr, int m_city[101][101])
{
    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, m_city)) return {curr.i + 1, curr.j - 1}; else return NOT_YET;
        case 2: if (e_valid(curr.i, curr.j - 1, m_city)) return {curr.i, curr.j - 1}; else return NOT_YET;
        case 3: if (e_valid(curr.i - 1, curr.j - 1, m_city)) return {curr.i - 1, curr.j - 1}; else return NOT_YET;
        case 4: if (e_valid(curr.i + 1, curr.j, m_city)) return {curr.i + 1, curr.j}; else return NOT_YET;
        case 5: if (e_valid(curr.i - 1, curr.j, m_city)) return {curr.i - 1, curr.j}; else return NOT_YET;
        case 6: if (e_valid(curr.i + 1, curr.j + 1, m_city)) return {curr.i + 1, curr.j + 1}; else return NOT_YET;
        case 7: if (e_valid(curr.i, curr.j + 1, m_city)) return {curr.i, curr.j + 1}; else return NOT_YET;
        case 8: if (e_valid(curr.i - 1, curr.j + 1, m_city)) 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);


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

    fclose(f);
}

void BFS(int m_dist[101][101], int st_i, int st_j)
{
    queue <coord> Q;

    m_dist[st_i][st_j] = 1;
    Q.push({st_i, st_j});

    coord curr, neigh;

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

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

struct solution
{
    coord x;
    int d;
};

solution solve()
{
    BFS(m_j, J.i, J.j);
    BFS(m_r, R.i, R.j);

    int d_min = INF_INT, i_min, j_min;

    for (int i = 0; i < nr_linii; i++)
        for (int j = 0; j < nr_col; j++)
            if (m_j[i][j] == m_r[i][j] && m_j[i][j] > 0 && m_j[i][j] < d_min)
            {
                d_min = m_j[i][j];
                i_min = i;
                j_min = j;
            }

    return {{i_min + 1, j_min + 1}, d_min};
}


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);

    fclose(f);
}