Cod sursa(job #2334730)

Utilizator CozminelDanielLupu Cosmin-Daniel CozminelDaniel Data 2 februarie 2019 22:27:47
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <bits/stdc++.h>
#define inf 1e9

using namespace std;

queue < pair < int, int > > Q;
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, -1, -1, 0, 1, 1};
char a[102][102];
int n, m, R[102][102], J[102][102];
int xr, yr, xj, yj;

void Citire()
{
    char x;
    ifstream fin("rj.in");
    fin >> n >> m;
    fin.get();
    for(int i = 1; i <= n; i++)
        fin.getline(a[i] + 1, 102);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
    {
        if(a[i][j] == 'R')
        {
            xr = i;
            yr = j;
        }
        else
            if(a[i][j] == 'J')
            {
                xj = i;
                yj = j;
            }
    }
    fin.close();
}

void Initializare()
{
    int i, j;
    for(i = 0; i < n + 2; i++)
        a[i][0] = a[i][m + 1] = 'X';
    for(i = 0; i < m + 2; i++)
        a[0][i] = a[n + 1][i] = 'X';
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            R[i][j] = J[i][j] = inf;
}

void Lee(int x, int y, int mat[102][102])
{
    int i, j, ii, jj, k;
    mat[x][y] = 1;
    Q.push({x, y});
    while(!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for(k = 0; k < 8; k++)
        {
            ii = i + dx[k];
            jj = j + dy[k];
            if(a[ii][jj] != 'X' && mat[ii][jj] > mat[i][j] + 1)
            {
                mat[ii][jj] = mat[i][j] + 1;
                Q.push({ii, jj});
            }
        }
    }
}

void Afisare()
{
    ofstream fout("rj.out");
    Lee(xr, yr, R);
    Lee(xj, yj, J);
    int i, j, imin = n, jmin = m, M = inf;

    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            if(R[i][j] == J[i][j] && R[i][j] != inf && a[i][j] != 1 && M > R[i][j])
            {
                M = R[i][j];
                imin = i;
                jmin = j;
            }
    fout << M << " " << imin << " " << jmin << "\n";
    fout.close();
}

int main()
{
    Citire();
    Initializare();
    Afisare();
    return 0;
}