Cod sursa(job #2609018)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 2 mai 2020 01:03:43
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("rj.in");
ofstream g ("rj.out");

int a[128][128], b[128][128], ir, ij, jr, jj, n, m, tmin = INT_MAX, x, y;
char s[128];
const int di[]= {-1, 1, -1, 1, 0, 0, 1, -1}, dj[] = {1, -1, -1, 1, 1, -1, 0, 0};

void Lee1 () {
    queue < pair < int , int > > Q;
    Q.push (make_pair (ir, jr));
    a[ir][jr] = 1;
    while (!Q.empty()) {
        int i = Q.front().first, j = Q.front().second;
        for (int k = 0; k < 8; ++k) {
            int iv = i + di[k], jv = j + dj[k];
            if (iv > 0 && jv > 0 && iv <= n && jv <= m && a[iv][jv] == 0) {
                a[iv][jv] = a[i][j] + 1;
                Q.push (make_pair(iv, jv));
            }
        }
        Q.pop();
    }
}

void Lee2 () {
    queue < pair < int , int > > Q;
    Q.push (make_pair (ij, jj));
    b[ij][jj] = 1;
    while (!Q.empty()) {
        int i = Q.front().first, j = Q.front().second;
        for (int k = 0; k < 8; ++k) {
            int iv = i + di[k], jv = j + dj[k];
            if (iv > 0 && jv > 0 && iv <= n && jv <= m && b[iv][jv] == 0) {
                b[iv][jv] = b[i][j] + 1;
                Q.push (make_pair(iv, jv));
            }
        }
        Q.pop();
    }
}

int main() {
    f >> n >> m;
    f.get();
    for (int i = 1; i <= n; ++i) {
        f.getline(s, sizeof(s));
        for (int j = 0; j < strlen(s); ++j)
        if (s[j] == 'X') a[i][j + 1] = b[i][j + 1] = -1;
        else if (s[j] == 'R') ir = i, jr = j + 1;
        else if (s[j] == 'J') ij = i, jj = j + 1;
    }
    Lee1();Lee2();
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
    if (a[i][j] == b[i][j] && a[i][j] > 0 && a[i][j] < tmin) {
        tmin = a[i][j];
        x = i;
        y = j;
    }
    g << tmin << " " << x << " " << y << '\n';
    f.close();
    g.close();
    return 0;
}