Cod sursa(job #2865224)

Utilizator PopaMihaimihai popa PopaMihai Data 8 martie 2022 17:12:03
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

typedef pair < int, int > PII;
const int NMAX = 103;

struct str
{
    int x;
    int y;
    int val;
};

int N, M;
int v[NMAX][NMAX];
int d1[NMAX][NMAX], d2[NMAX][NMAX];
bool sel[NMAX][NMAX];

PII romeo, julieta;

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

static inline void Reset()
{
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= M; ++j)
            sel[i][j] = false;
    return;
}

static inline bool Inbounds(PII a)
{
    return (1 <= a.first && a.first <= N && 1 <= a.second && a.second <= M);
}

static inline void Lee1(PII start)
{
    Reset();
    queue < PII > q;
    q.push(start);

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 8; ++i) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(Inbounds({xx, yy}) && (!sel[xx][yy] || (sel[xx][yy] && d1[xx][yy] > d1[x][y] + 1)) && v[xx][yy] != -1) {
                q.push({xx, yy});
                sel[xx][yy] = true;
                d1[xx][yy] = d1[x][y] + 1;
            }
        }
    }

    return;
}

static inline void Lee2(PII start)
{
    Reset();
    queue < PII > q;
    q.push(start);

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 8; ++i) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(Inbounds({xx, yy}) && (!sel[xx][yy] || (sel[xx][yy] && d2[xx][yy] > d2[x][y] + 1)) && v[xx][yy] != -1) {
                q.push({xx, yy});
                sel[xx][yy] = true;
                d2[xx][yy] = d2[x][y] + 1;
            }
        }
    }

    return;
}

static inline void Read()
{
    fin >> N >> M;
    char x;
    for(int i = 1; i <= N; ++i) {
        fin.get();
        for(int j = 1; j <= M; ++j) {
            fin.get(x);
            if(x == 'R')
                romeo = {i, j};
            if(x == 'J')
                julieta = {i, j};
            if(x == 'X')
                v[i][j] = -1;
        }
    }
    return;
}

static inline str mymin(str a, str b)
{
    return (a.val < b.val ? a : b);
}

int main()
{
    Read();
    Lee1(romeo);
    Lee2(julieta);

    str ans = {0, 0, 1000000};
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            if(d1[i][j] == d2[i][j] && d1[i][j] != 0)
                ans = mymin(ans, {i, j, d1[i][j]});

    fout << ans.val + 1 << " " << ans.x << " " << ans.y << '\n';

    return 0;
}