Mai intai trebuie sa te autentifici.

Cod sursa(job #2762665)

Utilizator DragosC1Dragos DragosC1 Data 9 iulie 2021 11:11:03
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;

char s[101];
int n, m;

int a[101][101];
int romeo[101][101];
int juliet[101][101];

int isr, jsr;
int isj, jsj; 
int Min, iintalnire, jintalnire;

void read() {
    int i, j;
    ifstream f("rj.in");
    f >> n >> m; f.get();
    for (i = 1; i <= n; i++) {
        f.getline(s, 101);
        for (j = 0; j < m; j++) 
            if (s[j] == 'R') 
                isr = i, jsr = j + 1;
            else if (s[j] == 'J')
                isj = i, jsj = j + 1;
            else if (s[j] == 'X')
                a[i][j + 1] = 1; 
    }
}

const int di[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dj[] = {0, 1, 0, -1, -1, 1, -1, 1};

queue<pair<int, int>> Q;

bool inside(int i, int j) {
    if (i >= 1 && j >= 1 && i <= n && j <= m)
        return 1;
    return 0;
}

void lee(int istart, int jstart, int mat[][101]) {
    int i, j, inou, jnou, k;
    mat[istart][jstart] = 1;
    Q.push({istart, jstart});
    while (!Q.empty()) {
        i = Q.front().first, j = Q.front().second;
        for (k = 0; k < 8; k++) {
            inou = i + di[k], jnou = j + dj[k];
            if (inside(inou, jnou) && a[inou][jnou] == 0 && mat[inou][jnou] == 0) {
                Q.push({inou, jnou});
                mat[inou][jnou] = mat[i][j] + 1;
            }
        }
        Q.pop();
    }
}

void solve() {
    // un lee pentru romeo
    lee(isr, jsr, romeo);

    // un lee pentru juliet
    lee(isj, jsj, juliet);

    // punctul de intalnire
    int i, j;
    Min = 1e9;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (romeo[i][j] > 0 && juliet[i][j] > 0 && romeo[i][j] == juliet[i][j] && romeo[i][j] < Min) {
                Min = romeo[i][j];
                iintalnire = i, jintalnire = j;
            }

}

void output() {
    ofstream g("rj.out");
    g << Min << ' ' << iintalnire << ' ' << jintalnire;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}