Cod sursa(job #2153707)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 6 martie 2018 13:53:24
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <bits/stdc++.h>
using namespace std;

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

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};

string str; deque<pair<int, int>> que;
int mat[DIM][DIM], dst[2][DIM][DIM];

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) {
    int n, m;
    in >> n >> m;

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

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

        for (int j = 0; j < str.size(); ++j) {
            if (str[j] == 'R')
                p1 = make_pair(i, j + 1);
            if (str[j] == 'J')
                p2 = make_pair(i, j + 1);
            if (str[j] == 'X')
                mat[i][j + 1] = 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] == dst[1][i][j] && dst[0][i][j] < tmn) {
            tmn = dst[0][i][j];
            fn = make_pair(i, j);
        }
    } }

    out << tmn << " " << fn.first << " " << fn.second;

    return 0;
}