Cod sursa(job #2162406)

Utilizator SilasiMariusSilasi Marius-Adrian SilasiMarius Data 12 martie 2018 10:46:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

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

const int DIM = 105;
const int Inf = 0x3f3f3f3f;
const int di[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dj[] = {-1, 0, 1, 1, 1, 0, -1, -1};
struct Cel{
    int x, y;
};
int N, M;
char a[DIM][DIM];
int cR[DIM][DIM];
int cJ[DIM][DIM];

void Read();
void Lee(Cel start, int c[DIM][DIM]);
bool OK(int i, int j);

int main()
{
    Read();

  /*  for (int i = 1; i <= N; ++i)
        fout << a[i] + 1 << '\n';   */

    Cel R, J;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
        {
            if ( a[i][j] == 'R' )
                R = {i, j};
            if ( a[i][j] == 'J' )
                J = {i, j};
        }

    Lee(R, cR);
    Lee(J, cJ);

    int is{-1}, js;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            if ( cR[i][j] == cJ[i][j] )
                if ( is == -1 || cR[i][j] < cR[is][js] )
                    is = i, js = j;

    fout << cR[is][js] << ' ' << is << ' ' << js << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> N >> M; fin.get();
    for (int i = 1; i <= N; ++i)
        fin.getline(a[i] + 1, DIM);
}

void Lee(Cel start, int c[DIM][DIM])
{
    for (int i = 0; i < DIM; ++i)
        for (int j = 0; j < DIM; ++j)
            c[i][j] = Inf;

    queue<Cel> Q;
    Q.push(start);
    c[start.x][start.y] = 1;
    while (!Q.empty())
    {
        int i = Q.front().x;
        int j = Q.front().y;
        Q.pop();

        for (int k = 0; k < 8; ++k)
        {
            int iv = i + di[k];
            int jv = j + dj[k];

            if ( OK(iv, jv) && c[iv][jv] > c[i][j] + 1 )
            {
                c[iv][jv] = c[i][j] + 1;
                Q.push( {iv, jv} );
            }
        }
    }
}

bool OK(int i, int j)
{
    return i >= 1 && i <= N && j >= 1 && j <= M && a[i][j] != 'X';
}