Cod sursa(job #1234418)

Utilizator assa98Andrei Stanciu assa98 Data 27 septembrie 2014 13:04:13
Problema Rj Scor 100
Compilator cpp Status done
Runda pregatire_bb_ Marime 1.73 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

#define pe pair<int, int>
#define fi first
#define se second
#define mp make_pair

using namespace std;

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

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

string s[MAX_N];
int d[2][MAX_N][MAX_N];
int n, m;

inline bool inborder(const pe &x) {
    return x.fi >= 1 && x.fi <= n && x.se >= 1 && x.se <= m;
}

void bfs(int x, int y, int d[MAX_N][MAX_N]) {
    queue<pe> Q;
    Q.push(mp(x, y));
    d[x][y] = 1;
    while(!Q.empty()) {
        pe nod = Q.front();
        Q.pop();
        for(int i = 0; i < 8; i++) {
            pe nnod = mp(nod.fi + dx[i], nod.se + dy[i]);
            if(inborder(nnod) && !d[nnod.fi][nnod.se] && s[nnod.fi][nnod.se] == ' ') {
                d[nnod.fi][nnod.se] = d[nod.fi][nod.se] + 1;
                Q.push(nnod);
            }
        }
    }
}

int main() {    
    fin >> n >> m;
    for(int i = 0; i <= n; i++) {
        getline(fin, s[i]);
        s[i] = 'X' + s[i];
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(s[i][j] == 'R') {
                bfs(i, j, d[0]);
            }
            else if(s[i][j] == 'J') {
                bfs(i, j, d[1]);
            }
        }
    }

    int ans = n * m;
    pe poz = mp(0, 0);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(d[0][i][j] == d[1][i][j] && d[0][i][j]) {
                if(d[0][i][j] < ans) {
                    ans = d[0][i][j];
                    poz = mp(i, j);
                }
            }
        }
    }
    
    fout << ans << ' ' << poz.fi << ' ' << poz.se;
    
    return 0;
}