Cod sursa(job #2797300)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 9 noiembrie 2021 18:12:02
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

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

const int Nmax = 101;

struct Pos {
    int l, c;

    Pos(int lin = 0, int col = 0) : l(lin), c(col) {}
};

int n, m;
Pos R, J;
int adR[Nmax][Nmax];
int adJ[Nmax][Nmax];

int dl[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc[] = {0, 1, 1, 1, 0, -1, -1, -1};

void border() {
    for (int i = 0; i <= n + 1; ++i) {
        adR[i][0] = adR[i][m + 1] = adJ[i][0] = adJ[i][m + 1] = -1;
    }

    for (int j = 0; j <= m + 1; ++j) {
        adR[0][j] = adR[n + 1][j] = adJ[0][j] = adJ[n + 1][j] = -1;
    }
}

void read() {
    char line[Nmax];

    fin >> n >> m;
    fin.get();

    for (int i = 1; i <= n; ++i) {
        fin.getline(line, Nmax);

        for (int j = 0; j < m; ++j) {
            if (line[j] == 'R') {
                R.l = i;
                R.c = j + 1;
            } else if (line[j] == 'J') {
                J.l = i;
                J.c = j + 1;
            } else if (line[j] == 'X') {
                adR[i][j + 1] = adJ[i][j + 1] = -1;
            }
        }
    }

    fin.close();
}

void Lee(Pos &start, int ad[Nmax][Nmax]) {
    Pos current;
    int lin, col;
    queue<Pos> Q;

    Q.push(start);
    ad[start.l][start.c] = 1;

    while (!Q.empty()) {
        current = Q.front(); Q.pop();

        for (int i = 0; i < 8; ++i) {
            lin = current.l + dl[i];
            col = current.c + dc[i];

            if (ad[lin][col] == 0) {
                Q.push(Pos(lin, col));
                ad[lin][col] = ad[current.l][current.c] + 1;
            }
        }
    }
}

void getOptimalPos() {
    border();
    Lee(R, adR);
    Lee(J, adJ);

    int minDist = Nmax * Nmax;
    Pos minPos;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (adR[i][j] > 0 && adR[i][j] == adJ[i][j] && adR[i][j] < minDist) {
                minDist = adR[i][j];
                minPos = Pos(i, j);
            }
        }
    }

    fout << minDist << ' ' << minPos.l << ' ' << minPos.c;
}

int main() {
    read();
    getOptimalPos();

    fout.close();
    return 0;
}