Cod sursa(job #1655857)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 18 martie 2016 13:50:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

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

const int MAXN = 101;
const int DIRECTIONS = 8;

int n, m;
char A[MAXN][MAXN];

const int dirX[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dirY[] = {0, 1, 1, 1, 0, -1, -1, -1};

int dR[MAXN][MAXN];
int dJ[MAXN][MAXN];

int rX;
int rY;

int jX;
int jY;

void read() {
    in >> n;
    in >> m;

    in.get();

    string s;

    for(int i = 1; i <= n; i++) {
        getline(in, s);
        for(int j = 0; j < s.size(); j++) {
            A[i][j + 1] = s[j];

            if(s[j] == 'J')
                jX = i, jY = j + 1;
            if(s[j] == 'R')
                rX = i, rY = j + 1;
        }
    }
}

bool checkRomeo(int i, int j) {
    if(A[i][j] == 'X')
        return false;

    if(i < 0 || i >= n)
        return false;
    if(j < 0 || j >= m)
        return false;

    if(dR[i][j] > 0)
        return false;

    return true;
}

bool checkJuliet(int i, int j) {

    if(A[i][j] == 'X')
        return false;

    if(i < 0 || i > n)
        return false;
    if(j < 0 || j > m)
        return false;

    if(dJ[i][j] > 0)
        return false;

    return true;
}


void solve() {
    queue< pair<int, int> > qR;
    queue< pair<int, int> > qJ;

    dR[rX][rY] = 1;
    dJ[jX][jY] = 1;

    qR.push(make_pair(rX, rY));
    qJ.push(make_pair(jX, jY));

    while(qR.empty() == false && qJ.empty() == false) {
        int rX = qR.front().first;
        int rY = qR.front().second;

        int jX = qJ.front().first;
        int jY = qJ.front().second;

        qR.pop();
        qJ.pop();

        for(int i = 0; i < DIRECTIONS; i++) {
            if(checkRomeo(rX + dirX[i], rY + dirY[i]) == true ) {
                dR[rX + dirX[i]][rY + dirY[i]] = dR[rX][rY] + 1;
                qR.push(make_pair(rX + dirX[i], rY + dirY[i]));
            }

            if(checkJuliet(jX + dirX[i], jY + dirY[i]) == true) {
                dJ[jX + dirX[i]][jY + dirY[i]] = dJ[jX][jY] + 1;
                qJ.push(make_pair(jX + dirX[i], jY + dirY[i]));
            }
        }

    }

    int minn = 1 << 20;
    int x = 0;
    int y = 0;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(dR[i][j] == dJ[i][j]) {
                if(dR[i][j] < minn && dR[i][j] > 0) {
                    minn = dR[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    }

    out << minn << " " << x << " " << y <<"\n";

}

void write() {

    out << "MATRICE\n";

    out << "ROMEO \n";
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j<= m; j++) {
            out << A[i][j] << " ";
        }
        out << endl;
    }

    out << "ROMEO \n";
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j<= m; j++) {
            out << dR[i][j] << " ";
        }
        out << endl;
    }
    out << "\nJULIETA \n";
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j<= m; j++) {
            out << dJ[i][j] << " ";
        }
        out << endl;
    }

}

int main() {
    read();
    solve();
   // write();
    return 0;
}