Cod sursa(job #3237190)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 6 iulie 2024 12:00:50
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const int MAX_N = 105;
const int dir[2][8] = {{0, 0, 1, -1, 1, 1, -1, -1}, 
                       {1, -1, 0, 0, 1, -1, 1, -1}};

int n, m;
bool map[MAX_N][MAX_N];
pair <int, int> julietStart;
pair <int, int> romeoStart;

int distancesRomeo[MAX_N][MAX_N];
int distancesJuliet[MAX_N][MAX_N];
queue <pair <int, int>> q;

pair <int, int> ansPos;
int ansDist = INF;

void ReadMap() {
    fin >> n >> m;

    // Read for newline
    string s;
    getline(fin, s);

    for (int i = 0; i < n; i++) {
        getline(fin, s);

        for (int j = 0; j < s.size(); j++) {
            if (s[j] == 'J') {
                julietStart = {i, j};
            }
            else if (s[j] == 'R') {
                romeoStart = {i, j};
            }
            else if (s[j] == 'X') {
                map[i][j] = 1;
            }
        }
    }
}

void InitDistances(int distances[MAX_N][MAX_N]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            distances[i][j] = INF;
        }
    }
}

bool InBounds(pair <int, int> pos) {
    if (pos.first < 0 || pos.second < 0 || pos.first >= n || pos.second >= m) {
        return false;
    }
    return true;
}

void BFS(pair <int, int> start, int distances[MAX_N][MAX_N]) {
    InitDistances(distances);

    distances[start.first][start.second] = 1;
    q.push(start);

    while (!q.empty()) {
        auto currPos = q.front();
        q.pop();

        for (int i = 0; i < 8; i++) {
            auto newPos = currPos;
            newPos.first += dir[0][i];
            newPos.second += dir[1][i];

            if (!InBounds(newPos) || map[newPos.first][newPos.second] ||
                    distances[newPos.first][newPos.second] <
                    distances[currPos.first][currPos.second] + 1) {
                continue;
            }

            distances[newPos.first][newPos.second] = distances[currPos.first][currPos.second] + 1;
            q.push(newPos);
        }
    }
}

void ComputeAnswer() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (distancesJuliet[i][j] != distancesRomeo[i][j] || distancesRomeo[i][j] > ansDist) {
                continue;
            }
            ansDist = distancesRomeo[i][j];
            ansPos = {i + 1, j + 1};
        }
    }
}

void WriteAnswer() {
    fout << ansDist << ' ' << ansPos.first << ' ' << ansPos.second << '\n';
}

int main() { 
    ReadMap();
    BFS(julietStart, distancesJuliet);
    BFS(romeoStart, distancesRomeo);
    ComputeAnswer();
    WriteAnswer();

    return 0;
}