Cod sursa(job #1617489)

Utilizator DeehoroEjkoliPop Darian DeehoroEjkoli Data 27 februarie 2016 14:26:58
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <queue>
#define nmax 105
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

int n, m, map_romeo[nmax][nmax], map_juliette[nmax][nmax];

queue < pair < int, int > > tail;

bool is_ok(int x, int y) {
    if (x < 1 or y < 1 or x > n or y > m or map_romeo[x][y] != 0)
        return false;
    return true;
}

bool is_ok_s(int x, int y) {
    if (x < 1 or y < 1 or x > n or y > m or map_juliette[x][y] != 0)
        return false;
    return true;
}

int main()
{
    int r_x, r_y, j_x, j_y, min_time = 10005, r_1, r_2, r_3;
    int d_x[8] = {-1, 0, 1, 0, 1, 1, -1, -1};
    int d_y[8] = {0, 1, 0, -1, 1, -1, -1, 1};
    fin >> n >> m;
    fin.get();
    for (int i = 1; i <= n; ++i) {
        string x;
        getline(fin, x);
        for (int j = 0; j <= x.size() - 1; ++j) {
            (x[j] == 'R')? r_x = i, r_y = j + 1, map_romeo[r_x][r_y] = 1: true;
            (x[j] == 'J')? j_x = i, j_y = j + 1, map_juliette[j_x][j_y] = 1: true;
            (x[j] == 'X')? map_romeo[i][j + 1] = -1, map_juliette[i][j + 1] = -1: true;
        }
    }
    tail.push(make_pair(r_x, r_y));
    while (!tail.empty()) {
        int x = tail.front().first;
        int y = tail.front().second;
        tail.pop();
        for (int k = 0; k <= 7; ++k)
            if (is_ok(x + d_x[k], y + d_y[k])) {
                map_romeo[x + d_x[k]][y + d_y[k]] = map_romeo[x][y] + 1;
                tail.push(make_pair(x + d_x[k], y + d_y[k]));
            }
    }
    tail.push(make_pair(j_x, j_y));
    while (!tail.empty()) {
        int x = tail.front().first;
        int y = tail.front().second;
        tail.pop();
        for (int k = 0; k <= 7; ++k)
            if (is_ok_s(x + d_x[k], y + d_y[k])) {
                map_juliette[x + d_x[k]][y + d_y[k]] = map_juliette[x][y] + 1;
                if (map_juliette[x + d_x[k]][y + d_y[k]] == map_romeo[x + d_x[k]][y + d_y[k]] and min_time > map_juliette[x + d_x[k]][y + d_y[k]]) {
                    r_1 = map_juliette[x + d_x[k]][y + d_y[k]];
                    r_2 = x + d_x[k];
                    r_3 = y + d_y[k];
                    min_time = map_juliette[x + d_x[k]][y + d_y[k]];
                }
                tail.push(make_pair(x + d_x[k], y + d_y[k]));
            }
    }
    fout << r_1 << " " << r_2 << " " << r_3;
}