Cod sursa(job #2660334)

Utilizator DiagrDiana Grigore Diagr Data 18 octombrie 2020 22:02:54
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int f1[8] = {0, 1, 0, -1, -1, 1, -1, 1};  //vectori de directie
int f2[8] = {1, 0, -1, 0, -1, 1,  1,-1};
int xr, yr, xj, yj, n, m, r[102][102], jl[102][102];
char lee[102][102];

void parcurgere(int xs, int ys, int d[102][102])
{
    pair<int, int> p;
    queue<pair<int,int>> q;
    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= m + 1; j++)
            d[i][j] = -1;
    q.push(make_pair(xs,ys));
    d[xs][ys] = 1;
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        for(int i = 0; i < 8; i++)
            if(lee[p.first + f1[i]][p.second + f2[i]] == ' ' && d[p.first + f1[i]][p.second + f2[i]] == -1)
            {
                d[p.first + f1[i]][p.second + f2[i]] = d[p.first][p.second] + 1;
                q.push(make_pair(p.first + f1[i], p.second + f2[i]));
            }
    }
}

int main() {
    f >> n >> m;
    //Bordam matricea pe margine cu 'X'
    for (int i = 0; i <= n + 1; i++) {
        lee[i][0] = 'X';
        lee[i][m + 1] = 'X';
    }
    for (int j = 0; j <= m + 1; j++) {
        lee[0][j] = 'X';
        lee[n + 1][j] = 'X';
    }

    char c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f.get(c);
            if(c != '\n')       //citire ciudata
                lee[i][j] = c;
            else
                j--;
            if (lee[i][j] == 'R') {
                xr = i;
                yr = j;
                lee[i][j] = ' '; //pastram coordonatele lui Romeo
            }
            if (lee[i][j] == 'J') {
                xj = i;
                yj = j;
                lee[i][j] = ' ';    //pastram coordonatele Julietei
            }
            if(j == m) f.get(); //citire /n
        }
    }

    parcurgere(xj, yj, r);
    parcurgere(xr, yr, jl);

    int dist = INT_MAX, xf=-1, yf=-1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (r[i][j] == jl[i][j])
                if (r[i][j] < dist && r[i][j] != -1)
                {
                    dist = r[i][j];
                    xf = i;
                    yf = j;
                }
    g << dist << ' ' << xf << ' ' << yf;
    return 0;
}