Cod sursa(job #2270172)

Utilizator Mathe13Mathe Andrei Mathe13 Data 27 octombrie 2018 09:50:01
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

struct Coord {
    int i, j;
};


queue <Coord> Q;
int N, M, matrix_R[110][110], matrix_J[110][110], t_min;

Coord R, J, meeting_point;

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


void Copy_Matrix()
{
    for (int i = 0; i < N+1; ++i)
        for (int j = 0; j < M+1; ++j)
            matrix_J[i][j] = matrix_R[i][j];
}

void Border()
{
    for (int j = 0; j <= M+1; ++j){
        matrix_R[0][j] = -1;
        matrix_R[N+1][j] = -1;
        matrix_J[0][j] = -1;
        matrix_J[N+1][j] = -1;
    }
    for (int i = 1; i <= N; ++i){
        matrix_R[i][0] = -1;
        matrix_R[i][M+1] = -1;
        matrix_J[i][0] = -1;
        matrix_J[i][M+1] = -1;
    }
}

void Solve()
{
    Q.push(J);
    matrix_J[J.i][J.j] = 1;

    /// Julieta
    while (!Q.empty()){
        Coord nod = Q.front();
        Q.pop();

        for (int d = 0; d < 8; ++d){
            Coord elem;
            int ci, cj;
            ci = nod.i + di[d];
            cj = nod.j + dj[d];
            if (matrix_J[ci][cj] == 0){
                matrix_J[ci][cj] = 1 + matrix_J[nod.i][nod.j];
                elem.i = ci;
                elem.j = cj;
                Q.push(elem);
            }
        }
    }

    Q.push(R);
    matrix_R[R.i][R.j] = 1;

    /// Romeo
    while (!Q.empty()){
        Coord nod = Q.front();
        Q.pop();

        for (int d = 0; d < 8; ++d){
            Coord elem;
            int ci, cj;
            ci = nod.i + di[d];
            cj = nod.j + dj[d];
            if (matrix_R[ci][cj] == 0){
                matrix_R[ci][cj] = 1 + matrix_R[nod.i][nod.j];
                elem.i = ci;
                elem.j = cj;
                Q.push(elem);
            }
        }
    }

}

void Read()
{
    char cr;
    bool newline = false;
    fin >> N >> M;
    t_min = INT_MAX;

    Border();
    for (int i = 1; i <= N; ++i){
        if (!newline)
            fin.get(cr);
        else
            newline = false;
        for (int j = 1; j <= M; ++j){
            fin.get(cr);
            if (cr != '\n'){
                switch (cr){
                case 'X':
                    matrix_R[i][j] = -1;
                    break;
                case ' ':
                    matrix_R[i][j] = 0;
                    break;
                case 'R':
                    R.i = i;
                    R.j = j;
                    break;
                case 'J':
                    J.i = i;
                    J.j = j;
                    break;
                }
            }
            else{
                newline = true;
                break;
            }
        }
    }
    Copy_Matrix();
}

void Write()
{
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            if (matrix_R[i][j] == matrix_J[i][j] && matrix_R[i][j] != -1 && t_min > matrix_R[i][j]){
                t_min = matrix_R[i][j];
                meeting_point.i = i;
                meeting_point.j = j;
            }

    fout << t_min << " " << meeting_point.i << " " << meeting_point.j;
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}