Cod sursa(job #2573292)

Utilizator Ovidiu-AntonioOvidiu-Antonio Matei Ovidiu-Antonio Data 5 martie 2020 16:54:53
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

int romeo[105][105], julieta[105][105], n, m, x, y, tmin = 10000, t, d1[] = {-1, 1, 0, 0, -1, -1, 1, 1}, d2[] = {0, 0, -1, 1, -1, 1, -1, 1};
queue < pair < int, int > > rom;
queue < pair < int, int > > jul;

bool ok1(int i, int j) {
    if(i < 1 || j < 1 || i > n || j > m)
        return false;
    if(julieta[i][j] >= 1 || julieta[i][j] == -2)
        return false;
    return true;
}

void julietaSolve() {
    while(!jul.empty()) {
        int i = jul.front().first;
        int j = jul.front().second;
        for(int l = 0; l < 8; l++) {
            int ii = i + d1[l];
            int jj = j + d2[l];
            if(ok1(ii, jj)) {
                julieta[ii][jj] = julieta[i][j] + 1;
                jul.push(make_pair(ii, jj));
            }
        }
        jul.pop();
    }
}

bool ok(int i, int j) {
    if(i < 1 || j < 1 || i > n || j > m)
        return false;
    if(romeo[i][j] >= 1 || romeo[i][j] == -2)
        return false;
    return true;
}

void romeoSolve() {
    while(!rom.empty()) {
        int i = rom.front().first;
        int j = rom.front().second;
        for(int l = 0; l < 8; l++) {
            int ii = i + d1[l];
            int jj = j + d2[l];
            if(ok(ii, jj)) {
                romeo[ii][jj] = romeo[i][j] + 1;
                rom.push(make_pair(ii, jj));
            }
        }
        rom.pop();
    }
}

int main()
{
    char c[105];
    fin >> n >> m;
    fin.getline(c, 105);
    for(int i = 1; i <= n; i++) {
        fin.getline(c, 105);
        for(int j = 0; j < m; j++) {
            if(c[j] == 'R') {
                romeo[i][j + 1] = 1;
                rom.push(make_pair(i, j + 1));
            }
            if(c[j] == 'J') {
                julieta[i][j + 1] = 1;
                jul.push(make_pair(i, j + 1));
            }
            if(c[j] == 'X') {
                romeo[i][j + 1] = -2;
                julieta[i][j + 1] = -2;
            }
            if(c[j] == ' ') {
                romeo[i][j + 1] = -1;
                julieta[i][j + 1] = -1;
            }
        }
    }
    romeoSolve();
    julietaSolve();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(romeo[i][j] == julieta[i][j] && romeo[i][j] > 0) {
                t = romeo[i][j];
                if(t < tmin) {
                    tmin = t;
                    x = i;
                    y = j;
                }
            }
        }
    }
    fout << tmin << " " << x << " " << y;
    return 0;
}