Cod sursa(job #2477609)

Utilizator EckchartZgarcea Robert-Andrei Eckchart Data 20 octombrie 2019 19:31:42
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
const unsigned nr_dirs = 8;
const int dx[] = { -1, -1, 0, 1, 1,  1,  0, -1 },
dy[] = { 0,  1, 1, 1, 0, -1, -1, -1 };
unsigned N, M, res_min_line, res_min_col;  // 1 < N, M < 101
int A[103][103], B[103][103];
std::vector<int> result_vals(3);


struct Position
{
    int lin, col;
} Rom, Jul;


inline void border()
{
    for (unsigned i = 0; i <= N + 1; ++i)
    {
        A[i][0] = A[i][M + 1] = B[i][0] = B[i][M + 1] = -1;
    }
    for (unsigned j = 0; j <= M + 1; ++j)
    {
        A[0][j] = A[N + 1][j] = B[0][j] = B[N + 1][j] = -1;
    }
}


std::vector<int> lee()
{
    border();

    int val;
    bool ok = false;
    std::vector<int> cur_vals;

    std::queue<std::pair<unsigned, unsigned>> Q_Rom, Q_Jul;
    Q_Rom.push(std::make_pair(Rom.lin, Rom.col));
    Q_Jul.push(std::make_pair(Jul.lin, Jul.col));
    A[Rom.lin][Rom.col] = B[Jul.lin][Jul.col] = 1;

    while (!Q_Rom.empty())
    {
        std::pair<unsigned, unsigned> cur_pos_Rom = Q_Rom.front();
        Q_Rom.pop();

        for (unsigned i = 0; i < nr_dirs; ++i)
        {
            int new_line_Rom = cur_pos_Rom.first + dx[i];
            int new_col_Rom = cur_pos_Rom.second + dy[i];

            if (A[new_line_Rom][new_col_Rom] == 0)
            {
                A[new_line_Rom][new_col_Rom] = A[cur_pos_Rom.first][cur_pos_Rom.second] + 1;
                Q_Rom.push(std::make_pair(new_line_Rom, new_col_Rom));
            }
        }
    }
    while (!Q_Jul.empty())
    {
        std::pair<int, int> cur_pos_Jul = Q_Jul.front();
        Q_Jul.pop();

        for (unsigned i = 0; i < nr_dirs; ++i)
        {
            int new_line_Jul = cur_pos_Jul.first + dx[i];
            int new_col_Jul = cur_pos_Jul.second + dy[i];
            if (B[new_line_Jul][new_col_Jul] == 0)
            {
                B[new_line_Jul][new_col_Jul] = B[cur_pos_Jul.first][cur_pos_Jul.second] + 1;

                val = B[new_line_Jul][new_col_Jul];
                if (val >= A[new_line_Jul][new_col_Jul] &&
                    val - A[new_line_Jul][new_col_Jul] <= 1)
                {
                    return { val, new_line_Jul, new_col_Jul };
                }
                cur_vals = { val, cur_pos_Jul.first, cur_pos_Jul.second };
                ok = true;

                Q_Jul.push(std::make_pair(new_line_Jul, new_col_Jul));
            }
        }
    }
}



int main()
{
    std::ifstream fisierIN("rj.in");
    fisierIN >> N >> M; fisierIN.get();
    for (unsigned i = 1; i <= N; ++i)
    {
        for (unsigned j = 1; j <= M; ++j)
        {
            char cur_chr = fisierIN.get();
            if (cur_chr == 'X')
            {
                A[i][j] = B[i][j] = -1;
            }
            else if (cur_chr == 'R')
            {
                Rom.lin = i, Rom.col = j;
            }
            else if (cur_chr == 'J')
            {
                Jul.lin = i, Jul.col = j;
            }
        }
        fisierIN.get();
    }
    fisierIN.close();

    std::ofstream fisierOUT("rj.out");
    result_vals = lee();
    for (int val : result_vals)
    {
        fisierOUT << val << " ";
    }
    fisierOUT.close();
    return 0;
}