Cod sursa(job #2153792)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 6 martie 2018 14:30:51
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>
using namespace std;

const int DIM = 105;

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

deque<pair<int, int>> que;
bool mat[DIM][DIM]; int dst[2][DIM][DIM]; char str[DIM + 1];

void bfs(pair<int, int> st, int k, int n, int m) {
    dst[k][st.first][st.second] = 1;
    que.push_back(st);

    for (; que.size(); que.pop_front()) {
        pair<int, int> ps = que.front();

        for (int d = 0; d <= 7; ++d) {
            pair<int, int> nx = make_pair(ps.first + dx[d], ps.second + dy[d]);

            if (nx.first <= 0 || nx.first > n)
                continue;
            if (nx.second <= 0 || nx.second > m)
                continue;

            if (dst[k][nx.first][nx.second] == 0 && !mat[nx.first][nx.second]) {
                dst[k][nx.first][nx.second] = dst[k][ps.first][ps.second] + 1;
                que.push_back(nx);
            }
        }
    }
}

int main(void) {
    FILE *in = fopen("rj.in", "r");
    FILE *out = fopen("rj.out", "w");

    int n, m;
    fscanf(in, "%d %d\n", &n, &m);

    pair<int, int> p1, p2, fn;

    for (int i = 1; i <= n; ++i) {
        fgets(str + 1, DIM, in);

        for (int j = 1; j <= m; ++j) {
            if (str[j] == 'R')
                p1 = make_pair(i, j);
            if (str[j] == 'J')
                p2 = make_pair(i, j);
            if (str[j] == 'X')
                mat[i][j] = true;
        }
    }

    bfs(p1, 0, n, m);
    bfs(p2, 1, n, m);

    int tmn = 1e9;
    for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (!mat[i][j] && dst[0][i][j] > 0 && dst[0][i][j] == dst[1][i][j] && dst[0][i][j] < tmn) {
            tmn = dst[0][i][j];
            fn = make_pair(i, j);
        }
    } }

    fprintf(out, "%d %d %d\n", tmn, fn.first, fn.second);

    return 0;
}