Cod sursa(job #2710315)

Utilizator vladstefanVlad Oros vladstefan Data 22 februarie 2021 13:09:47
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb

// Problema rj

#include <fstream>
#include <iostream>
#include <cstring>
#include <string>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>

#define NMax 100

using namespace std;

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

int n, m;
int a[NMax + 3][NMax + 3], cine[NMax + 3][NMax + 3]; //cine == 1 => Romeo; cine == 2 => Julieta

struct pos {
    int i;
    int j;
} rm, jl;

queue<pos> q;

// algoritmul lui Lee

pos dm[8] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}; // mai intai se verifica patratele cu indicele mai mic al coloanei

void input() {
    fin >> n >> m;
    fin.ignore();
    string s;
    for (int i = 1; i <= n; ++i) {
        getline(fin, s);
        for (int j = 0; j < m; ++j) {
            if (s[j] == 'R') rm = {i, j + 1};
            else if (s[j] == 'J') jl = {i, j + 1};
            else if (s[j] == 'X') a[i][j + 1] = -1;
        }
    }
}

pos verif() {
    pos aux = q.front();
    q.pop();
    if (aux.i <= 0 || aux.i > n || aux.j <= 0 || aux.j > m) return {0, 0};
    for (auto t : dm) {
        if (a[aux.i + t.i][aux.j + t.j] == 0) {
            q.push({aux.i + t.i, aux.j + t.j});
            a[aux.i + t.i][aux.j + t.j] = a[aux.i][aux.j] + 1;
            cine[aux.i + t.i][aux.j + t.j] = cine[aux.i][aux.j];
        } else if (a[aux.i + t.i][aux.j + t.j] == a[aux.i][aux.j] + 1 && cine[aux.i + t.i][aux.j + t.j] != cine[aux.i][aux.j]) return {aux.i + t.i, aux.j + t.j};
    }
    return {0, 0};
}

void init() {
    a[rm.i][rm.j] = 1;
    cine[rm.i][rm.j] = 1;
    a[jl.i][jl.j] = 1;
    cine[jl.i][jl.j] = 2;
    q.push(rm);
    q.push(jl);
}

void solve() {
    pos t;
    for (t = {0, 0}; t.i == 0; t = verif());
    fout << a[t.i][t.j] << ' ' << t.i << ' ' << t.j;
}

int main() {
    input();
    init();
    solve();
}