Cod sursa(job #2336836)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 5 februarie 2019 16:35:50
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <fstream>
#include <queue>
#include <limits.h>
#define MAX 105
#define INF INT_MAX

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");
struct coord{
    int x, y;
};
queue < coord > Q;
int di[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dj[] = {1, 1, 0, -1, -1, -1, 0, 1};
int R[MAX][MAX];
int J[MAX][MAX];
int A[MAX][MAX];
int n, m;
int ir, jr, ij, jj;
bool verif(int i, int j){
    if (i < 1 || j < 1 || j > m || i > n){
        return false;
    }
    return true;
}
void alee(){
    Q.push({ir, jr});
    while (!(Q.empty())){
        int i = Q.front().x;
        int j = Q.front().y;
        Q.pop();
        for (int k = 0; k < 8; k++){
            int new_i = i + di[k];
            int new_j = j + dj[k];
            if (verif(new_i, new_j) && R[new_i][new_j] != -1 && R[new_i][new_j] > 0 && R[new_i][new_j] > R[i][j] + 1){
                R[new_i][new_j] = R[i][j] + 1;
                Q.push({new_i, new_j});
            }
        }
    }
    Q.push({ij, jj});
    while (!(Q.empty())){
        int i = Q.front().x;
        int j = Q.front().y;
        Q.pop();
        for (int k = 0; k < 8; k++){
            int new_i = i + di[k];
            int new_j = j + dj[k];
            if (verif(new_i, new_j) && J[new_i][new_j] != -1 && J[new_i][new_j] > 0 && J[new_i][new_j] > J[i][j] + 1){
                J[new_i][new_j] = J[i][j] + 1;
                Q.push({new_i, new_j});
            }
        }
    }
}
int main(){
    int rj = 0, ri = 0, mini = INF;
    fin >> n;
    fin >> m;
    fin.get();
    for (int i = 1; i <= n; i++){
        char C[256];
        fin.getline(C, 256);
        for (int j = 0; C[j] != '\0'; j++){
            if (C[j] == ' '){
                A[i][j + 1] = INF;
                R[i][j + 1] = INF;
                J[i][j + 1] = INF;
            }
            else{
                if (C[j] == 'X'){
                    A[i][j + 1] = -1;
                    R[i][j + 1] = -1;
                    J[i][j + 1] = -1;
                }
                else{
                    if (C[j] == 'R'){
                        A[i][j + 1] = INF;
                        R[i][j + 1] = INF;
                        J[i][j + 1] = INF;
                        ir = i;
                        jr = j + 1;
                    }
                    else{
                        A[i][j + 1] = INF;
                        R[i][j + 1] = INF;
                        J[i][j + 1] = INF;
                        ij = i;
                        jj = j + 1;
                    }
                }
            }
        }
    }
    R[ir][jr] = 0;
    J[ij][jj] = 0;
    alee();
    /*for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            fout << R[i][j] << " ";
        }
        fout << "\n";
    }
    fout << "\n";
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            fout << J[i][j] << " ";
        }
        fout << "\n";
    }
    return 0;*/
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (R[i][j] == J[i][j] && R[i][j] < mini && R[i][j] > 0){
                mini = R[i][j];
                ri = i;
                rj = j;
            }
        }
    }
    fout << mini + 1 << " " << ri << " " << rj;
    return 0;
}