Cod sursa(job #2221083)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 13 iulie 2018 02:32:36
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

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

const int di[10] = {-1, 1, 0, 0, -1, 1, 1, -1};
const int dj[10] = {0, 0, 1, -1, 1, 1, -1, -1};

int drom[105][105], djul[105][105];
int n, m, i, j, i2, j2, dir, x1, x2, y1, y2, tmin, xmin, ymin;

char c[105], mat[105][105];

queue < pair<int, int> > Q;

bool isOK (int i, int j)
{
    if (i < 1 || j < 1 || i > n || j > n)
        return false;
    if (mat[i][j] == 'X')
        return false;
    return true;
}

void Lee(int x0, int y0, int drum[105][105])
{
    int i, j, i2, j2, dir;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            drum[i][j]= 0;
    drum[x0][y0] = 1;
    Q.push({x0, y0});
    while (!Q.empty()){
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for (dir=0; dir<8; dir++){
            i2 = i + di[dir];
            j2 = j + dj[dir];
            if (isOK(i2, j2) && drum[i2][j2] == 0){
                drum[i2][j2] = drum[i][j] + 1;
                Q.push({i2, j2});
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    fin.get();
    for (i=1; i<=n; i++){
        fin.getline(c, m + 1);
        for (j=1; j<=m; j++){
            mat[i][j] = c[j-1];
            if (c[j-1] == 'R'){
                x1 = i;
                y1 = j;
            }
            if (c[j-1] == 'J'){
                x2 = i;
                y2 = j;
            }
        }
    }
    tmin = 105*105;
    Lee(x1, y1, drom);
    Lee(x2, y2, djul);
    for (i=1; i<=n; i++){
        for (j=1; j<=m; j++){
            if (drom[i][j] == djul[i][j]){
                if (drom[i][j] < tmin && drom[i][j] != 0){
                    tmin = drom[i][j];
                    xmin = i;
                    ymin = j;
                }
            }
        }
    }
    fout << tmin << " " << xmin << " " << ymin;
    return 0;
}