Cod sursa(job #2532897)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 28 ianuarie 2020 16:15:14
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <fstream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

using per = pair <int, int>;

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

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

const int NMAX = 105;

queue <per> q_r;
queue <per> q_j;

string a[NMAX];
int lee_R[NMAX][NMAX], lee_J[NMAX][NMAX];
int n, m;
per r, jul;

inline bool ok_R(int x, int y)
{
    per p = { x, y };
    return  x > 0 && y >= 0 && x <= n && y < m && lee_R[x][y] == 0 && p != r &&  a[x][y] != 'X';
}

inline bool ok_J(int x, int y)
{
    per p = { x, y };
    return  x > 0 && y >= 0 && x <= n && y < m && lee_J[x][y] == 0 && p != jul && a[x][y] != 'X';
}

void Lee()
{
    int x, y, nx, ny;

    while (!q_r.empty())
    {
        x = q_r.front().first, y = q_r.front().second;
        q_r.pop();
        for (int i = 0; i < 4; ++i)
        {
            nx = x + dx[i];
            ny = y + dy[i];
            if (ok_R(nx, ny))
            {
                q_r.push({ nx, ny });
                lee_R[nx][ny] = lee_R[x][y] + 1;
            }
        }
    }

    while (!q_j.empty())
    {
        x = q_j.front().first, y = q_j.front().second;
        q_j.pop();
        for (int i = 0; i < 4; ++i)
        {
            nx = x + dx[i];
            ny = y + dy[i];
            if (ok_J(nx, ny))
            {
                q_j.push({ nx, ny });
                lee_J[nx][ny] = lee_J[x][y] + 1;
            }
        }
    }
    
}

void solve()
{
    int x, y;
    int mini = NMAX + NMAX;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < m; ++j)
        {
            int val = max(lee_R[i][j], lee_J[i][j]);
            if (val && val < mini)
            {
                mini = val;
                x = i;
                y = j + 1;
            }

        }
    fout << mini << " " << x << " " << y << "\n";

}

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

    for (int i = 1; i <= n; ++i)
    {
        getline(fin, a[i]);
        for (int j = 0; j < m; ++j)
            if (a[i][j] == 'R')
                r = { i, j };
            else if (a[i][j] == 'J')
                jul = { i, j };
    }

    q_r.push(r);
    q_j.push(jul);

    Lee();

    solve();

    return 0;
}