Cod sursa(job #2525936)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 18 ianuarie 2020 01:39:32
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <queue>

#define x first
#define y second

using namespace std;

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

const int N = 105;

int n, m;
int R[N][N], J[N][N];
bool obstacle[N][N];

void bf(int dist[N][N], pair<int, int> startPos)
{
    queue<pair<int, int>> q;
    int dirx[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    int diry[] = {-1, -1, -1, 0, 1, 1, 1, 0};

    q.push(startPos);
    dist[startPos.x][startPos.y] = 1;
    while(!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();

        for(int dir = 0; dir < 8; dir++)
        {
            int dx = p.x + dirx[dir];
            int dy = p.y + diry[dir];

            if(dx < 1 || dx > n || dy < 1 || dy > m)
                continue;

            if(obstacle[dx][dy] || dist[dx][dy])
                continue;

            q.push({dx, dy});
            dist[dx][dy] = dist[p.x][p.y] + 1;
        }
    }
}

int main()
{
    fin >> n >> m;

    pair<int, int> rPos, jPos;
    char c;
    fin.get(c);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            fin.get(c);
            if(c == 'R')
                rPos = {i, j};
            else if(c == 'J')
                jPos = {i, j};
            else if(c == 'X')
                obstacle[i][j] = true;
        }
        fin.get(c);
    }

    bf(R, rPos);
    bf(J, jPos);

    pair<int, int> meetPoint;
    int distMin = n * n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(R[i][j] == J[i][j] && R[i][j] && R[i][j] < distMin)
            {
                distMin = R[i][j];
                meetPoint = {i, j};
            }

    fout << distMin << ' ' << meetPoint.x << ' ' << meetPoint.y << '\n';



    return 0;
}