Cod sursa(job #1894812)

Utilizator LittleWhoFeraru Mihail LittleWho Data 27 februarie 2017 16:06:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

#define MAX_N 100

using namespace std;

int j_town[MAX_N][MAX_N];
int r_town[MAX_N][MAX_N];
int n, m;

typedef pair<int, int> pos;
queue<pos> j_positions;
queue<pos> r_positions;

//int Rx, Ry;
//int Jx, Jy;

pos make_pos(int x, int y)
{
    return make_pair(x, y);
}

bool check_bounds(int x, int y)
{
    return x >= 0 && y >= 0 && x < n && y < m;
}

int x_dir[] = {-1, -1, 0, +1, + 1, +1, 0, -1};
int y_dir[] = {0, +1, +1, +1, 0, -1, -1, -1};

void solve(ofstream &out)
{
    int tmin = 1000000000;
    pos last = make_pos(0, 0);

    while (!j_positions.empty()) {
        pos p = j_positions.front();
        register int x = p.first;
        register int y = p.second;
        j_positions.pop();

        register int new_x, new_y;
        for (int i = 0; i < 8; i++) {
            new_x = x + x_dir[i];
            new_y = y + y_dir[i];

            if (check_bounds(new_x, new_y) && j_town[new_x][new_y] == 0) {
                j_town[new_x][new_y] = j_town[x][y] + 1;
                j_positions.push(make_pos(new_x, new_y));
            }
        }
    }

    while (!r_positions.empty()) {
        pos p = r_positions.front();
        register int x = p.first;
        register int y = p.second;
        r_positions.pop();

        register int new_x, new_y;
        for (int i = 0; i < 8; i++) {
            new_x = x + x_dir[i];
            new_y = y + y_dir[i];

            if (check_bounds(new_x, new_y) && r_town[new_x][new_y] == 0) {
                r_town[new_x][new_y] = r_town[x][y] + 1;
                r_positions.push(make_pos(new_x, new_y));
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j_town[i][j] != -1 && j_town[i][j] != 0 && j_town[i][j] == r_town[i][j] && tmin > j_town[i][j]) {
                tmin = j_town[i][j];
                last.first = i;
                last.second = j;
            }
        }
    }

    out << tmin << " " << last.first + 1 << " " << last.second + 1 << "\n";
}

int main()
{
    ifstream in("rj.in");
    ofstream out("rj.out");

    in >> n >> m;

    string temp; temp.reserve(MAX_N);
    getline(in, temp);
    for (int i = 0; i < n; i++) {
        getline(in, temp);
        for (int j = 0; j < m; j++) {
            switch (temp[j]) {
            case ' ':
                j_town[i][j] = r_town[i][j] = 0;
                break;
            case 'X':
                j_town[i][j] = r_town[i][j] = -1;
                break;
            case 'R':
                r_town[i][j] = 1;
                r_positions.push(make_pos(i, j));
                break;
            case 'J':
                j_town[i][j] = 1;
                j_positions.push(make_pos(i, j));
                break;
            }
        }
    }

    solve(out);

    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << j_town[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << r_town[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;*/


    in.close();
    out.close();

    return 0;
}