Cod sursa(job #2477767)

Utilizator EckchartZgarcea Robert-Andrei Eckchart Data 21 octombrie 2019 08:41:29
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <fstream>
#include <queue>  // std::queue
#include <utility>  // std::pair
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;  // 1 < N, M < 101
int A[103][103], B[103][103];


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


void lee()
{
    border();

    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;
                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();
    bool s = false;
    lee();
    std::ofstream fisierOUT("rj.out");
    for (unsigned i = 1; i <= N; ++i)
    {
        for (unsigned j = 1; j <= M; ++j)
        {
            if (A[i][j] > 0 && A[i][j] == B[i][j])
            {
                fisierOUT << A[i][j] << " " << i << " " << j;
                s = true;
                break;
            }
        }
        if (s)
        {
            break;
        }
    }
    fisierOUT.close();
    return 0;
}