Cod sursa(job #2660361)

Utilizator ioanapintilie07Pintilie Ioana ioanapintilie07 Data 19 octombrie 2020 02:28:26
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
//1 = JULIETA
//2 = ROMEO
//0 = LIBER
//-1 = INTERZIS

const int maxi = 1001;

int a[maxi][maxi], romeo[maxi][maxi], julieta[maxi][maxi];
queue<int> X, Y;

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

bool interior(int x, int y, int n, int m) {
    return !(x < 1 || x > n || y < 1 || y > m);
}

void lee(int x, int y, int n, int m, int lee[][maxi]) {
    int xx, yy;
    X.push(x);
    Y.push(y);
    lee[x][y] = 1;
    while (!X.empty()) {
        x = X.front();
        y = Y.front();
        X.pop();
        Y.pop();
        for (int i = 0; i < 8; ++i) {
            xx = x + dx[i];
            yy = y + dy[i];
            if (interior(xx, yy, n, m) && a[xx][yy] != -1 && (lee[xx][yy] > (lee[x][y] + 1) || lee[xx][yy] == -1)) {
                lee[xx][yy] = lee[x][y] + 1;
                X.push(xx);
                Y.push(yy);
               // cout << "Da";
            }
        }
    }
}

int main() {
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    int n, m, i, j, xr, yr, xj, yj, si = -1, sj = -1;
    char x[maxi];
    fin >> n >> m;
    fin.get();
    for(i = 1; i <= n; ++i) {
        fin.getline(x, maxi);
        for(j = 1; j <= m; ++j) {
            if (x[j-1] == 'R') {
                a[i][j] = 2;
                xr = i;
                yr = j;
            } else if (x[j-1] == 'J') {
                xj = i;
                yj = j;
                a[i][j] = 1;
            } else if (x[j-1] == ' ')
                a[i][j] = 0;
            else
                a[i][j] = -1;
            romeo[i][j] = julieta[i][j] = -1;
        }
    }
    int mini = 10000;
    lee(xr, yr, n, m, romeo);
    lee(xj, yj, n, m, julieta);
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            if (romeo[i][j] == julieta[i][j] && ((romeo[i][j] != -1 && romeo[i][j] < mini) || (romeo[i][j] == mini && j < sj))) {
                mini = romeo[i][j];
                si = i;
                sj = j;
            }
    fout << mini << " " << si << " " << sj;
    return 0;
}