Cod sursa(job #2665338)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 30 octombrie 2020 16:31:57
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

int n, m, i, j, k, x, y, rx, ry, jx, jy, min1, px[] = {-1, -1, -1, 0, 1, 1, 1, 0}, py[] = {-1, 0, 1, 1, 1, 0, -1, -1}, romeo[105][105], julieta[105][105];
char h[105][105];

int main() {

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

    queue<pair<int, int>> poz;

    f >> n >> m;
    f.get();
    for(i = 0; i < n; i++) {
        f.getline(h[i], 105);

        k = strlen(h[i]);
        while(k < m) {
            h[i][k] = ' ';
            k++;
        }
        h[i][m] = '\0';
        for(j = 0; j < m; j++) {
            romeo[i][j] = julieta[i][j] = 10005;
            if(h[i][j] == 'R') {
                rx = i;
                ry = j;
            }
            if(h[i][j] == 'J') {
                jx = i;
                jy = j;
            }
        }
    }
    f.close();

    poz.emplace(rx, ry);
    romeo[rx][ry] = 1;
    while(!poz.empty()) {
        i = poz.front().first;
        j = poz.front().second;
        poz.pop();
        for(k = 0; k < 8; k++)
            if(0 <= i + px[k] && i + px[k] < n && 0 <= j + py[k] && j + py[k] < m && h[i + px[k]][j + py[k]] != 'X'  && romeo[i][j] + 1 < romeo[i + px[k]][j + py[k]]) {
                romeo[i + px[k]][j + py[k]] = romeo[i][j] + 1;
                poz.emplace(i + px[k], j + py[k]);
            }
    }

    poz.emplace(jx, jy);
    julieta[jx][jy] = 1;
    while(!poz.empty()) {
        i = poz.front().first;
        j = poz.front().second;
        poz.pop();
        for(k = 0; k < 8; k++)
            if(0 <= i + px[k] && i + px[k] < n && 0 <= j + py[k] && j + py[k] < m && h[i + px[k]][j + py[k]] != 'X' && julieta[i][j] + 1 < julieta[i + px[k]][j + py[k]]) {
                julieta[i + px[k]][j + py[k]] = julieta[i][j] + 1;
                poz.emplace(i + px[k], j + py[k]);
            }
    }

    min1 = 10005;
    x = y = -1;
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            if(romeo[i][j] == julieta[i][j] && romeo[i][j] < min1) {
                min1 = romeo[i][j];
                x = i + 1;
                y = j + 1;
            }

    g << min1 << ' ' << x << ' ' << y << '\n';
    g.close();

    return 0;
}