Cod sursa(job #876870)

Utilizator toranagahVlad Badelita toranagah Data 12 februarie 2013 11:28:25
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");
const int MAX_N = 105;
const int INF = 1 << 30;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int N, M;
int romeo[MAX_N][MAX_N];
int juliet[MAX_N][MAX_N];
pair<int, int> romeo_start;
pair<int, int> juliet_start;
int sol_dist = INF, sol_x = 0, sol_y = 0;

void read_input();
void solve();
void write_output();
void bfs(int mat[MAX_N][MAX_N], pair<int, int> start);
bool in_bounds(int x, int y);

int main() {
    read_input();
    solve();
    write_output();
    return 0;
}

void read_input() {
    fin >> N >> M;
    fin.ignore();
    string row;
    for (int i = 1; i <= N; ++i) {
        getline(fin, row);
        for (int j = 0; j < M; ++j) {
            if (row[j] == 'X') {
                romeo[i][j+1] = juliet[i][j+1] = -1;
            } else if (row[j] == 'R') {
                romeo[i][j+1] = 0;
                juliet[i][j+1] = INF;
                romeo_start.first = i;
                romeo_start.second = j + 1;
            } else if (row[j] == 'J') {
                juliet[i][j+1] = 0;
                romeo[i][j+1] = INF;
                juliet_start.first = i;
                juliet_start.second = j + 1;
            } else {
                romeo[i][j+1] = juliet[i][j+1] = INF;
            }
        }
    }
}

void solve() {
    bfs(romeo, romeo_start);
    bfs(juliet, juliet_start);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (romeo[i][j] != -1 && romeo[i][j] == juliet[i][j]) {
                if (romeo[i][j] < sol_dist) {
                    sol_dist = romeo[i][j];
                    sol_x = i;
                    sol_y = j;
                }
            }
        }
    }
}

void bfs(int mat[MAX_N][MAX_N], pair<int, int> start) {
    queue<pair<int, int> > q;
    q.push(start);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        for (int k = 0; k < 4; ++k) {
            int xx = x + dx[k], yy = y + dy[k];
            if (in_bounds(xx, yy) && mat[xx][yy] >= 0) {
                if (mat[x][y] + 1 < mat[xx][yy]) {
                    mat[xx][yy] = mat[x][y] + 1;
                    q.push(make_pair(xx, yy));
                }
            }
        }
        q.pop();
    }
}

inline bool in_bounds(int x, int y) {
    if (x < 1 || x > N) return false;
    if (y < 1 || y > M) return false;
    return true;
}

void write_output() {
    fout << sol_dist << ' ' << sol_x << ' ' << sol_y;
}