Cod sursa(job #3214674)

Utilizator ioanabaduIoana Badu ioanabadu Data 14 martie 2024 12:10:14
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

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

struct point {int x, y;};

int n, m;
int julieta[105][105], romeo[105][105];
int row[] = {1, 0, -1, 0, 1, -1, 1, -1}, col[] = {0, 1, 0, -1, 1, -1, -1, 1};

bool insideMat (point a){
    return a.x >= 1 && a.x <= n && a.y >= 1 && a.y <= m;
}

void lee (int mat[105][105], point start){
    queue <point> q;
    point current, future;

    mat[start.x][start.y] = 1;
    q.push(start);

    while (!q.empty()){
        current = q.front();

        for (int k=0; k<8; ++k){
            future.x = current.x + row[k];
            future.y = current.y + col[k];

            if (insideMat(future) && mat[future.x][future.y] == 0){
                mat[future.x][future.y] = mat[current.x][current.y] + 1;
                q.push(future);
            }
        }
        q.pop();
    }
}

bool valid (int i, int j){
    return julieta[i][j] != 0 && julieta[i][j] != -1 && romeo[i][j] != 0 && romeo[i][j] != -1;
}

int main()
{
    point startJulieta, startRomeo;

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

    char c[105];
    for (int i=1; i<=n; ++i){
        in.getline(c, 105);
        for (int j=1; j<=m; ++j){
            if (c[j-1] == 'X'){
                julieta[i][j] = -1;
                romeo[i][j] = -1;
            }
            else if (c[j-1] == 'R'){
                startRomeo.x = i;
                startRomeo.y = j;
            }
            else if (c[j-1] == 'J'){
                startJulieta.x = i;
                startJulieta.y = j;
            }
        }
    }

    lee (julieta, startJulieta);
    lee (romeo, startRomeo);

    int ans = INT_MAX;
    point meetup;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            if (julieta[i][j] == romeo[i][j] && valid(i, j)){
                if (ans > julieta[i][j]){
                    ans = julieta[i][j];
                    meetup.x = i;
                    meetup.y = j;
                }
            }
        }
    }

    out << ans << ' ' << meetup.x << ' ' << meetup.y;

    return 0;
}