Cod sursa(job #2668211)

Utilizator tudosemihaitudose mihai tudosemihai Data 4 noiembrie 2020 17:27:44
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

std::ifstream in("rj.in");
std::ofstream out("rj.out");

int n, m, rX, rY, jX, jY, rPoz, jPoz;
int cautR[101][101], cautJ[101][101], graph[101][101];


struct Coordinate{
    int x=0,y=0;
};

std::vector<Coordinate> romeo,julieta,solutie;

void cautareBFS(int x1, int y1, int x2, int y2){
    int depX[8]={  0, 0, 1, 1, 1, -1,-1,-1};
    int depY[8]={ -1, 1,-1, 0, 1, -1, 0, 1};

    for (int i = 0; i < 8; i++) {
        int x = x1 + depX[i], y = y1 + depY[i];
        Coordinate xy;
        xy.x = x;
        xy.y = y;
//        std::cout << "romeo looking at: " << x << " " << y << '\n';
        if(graph[x][y]>0 && cautR[x][y] == 0){
            cautR[x][y] = cautR[x1][y1] + 1;
//            std::cout << "and its free \n" << cautR[x][y] << '\n';

            if(cautJ[x][y]>0) {
                solutie.push_back(xy);
//                std::cout << "solutie romeo de pe: " << x1 << " " << y1 << "\n               spre: " << x << " " << y << '\n';
            }
            else{
                romeo.push_back(xy);
            }
        }
    }
    for (int i = 0; i < 8; i++) {
        int x = x2 + depX[i], y = y2 + depY[i];
        Coordinate xy;
        xy.x = x;
        xy.y = y;
//        std::cout << "juliet looking at: " << x << " " << y << '\n';
        if(graph[x][y]>0 && cautJ[x][y] == 0){
            cautJ[x][y] = cautJ[x2][y2] + 1;
//            std::cout << "and its free \n" << cautJ[x][y] << '\n';
            if(cautR[x][y]>0) {
                solutie.push_back(xy);
//                std::cout << "solutie julieta de pe: " << x2 << " " << y2 << "\n                 spre: " << x << " " << y << '\n';
            }
            else
                julieta.push_back(xy);
        }
    }
    if(rPoz<romeo.size() && jPoz<julieta.size())
    {
        x1 = romeo[rPoz].x;
        y1 = romeo[rPoz++].y;
        x2 = julieta[jPoz].x;
        y2 = julieta[jPoz++].y;
        cautareBFS(x1,y1,x2,y2);
    }
    if(rPoz<romeo.size())
    {
        x1 = romeo[rPoz].x;
        y1 = romeo[rPoz++].y;
        cautareBFS(x1,y1,x2,y2);
    }
    if(jPoz<julieta.size())
    {
        x2 = julieta[jPoz].x;
        y2 = julieta[jPoz++].y;
        cautareBFS(x1,y1,x2,y2);
    }
}

int main() {

    in >> n >> m;

    for (int i = 0; i <= n ; i++) {
        graph[i][0] = graph[0][i] = -2;
    }
    char citire_in_cplusplus[100];
    in.getline(citire_in_cplusplus,m);
    for (int i = 0; i < n; i++) {
        char linie[101];
        in.getline(linie,m+1);
        for(int j = 0; j < m; j++) {
            if(linie[j]=='X')
                graph[i+1][j+1]= -1;
            else if (linie[j]=='R'){
                rX=i+1;
                rY=j+1;
            }
            else if(linie[j]=='J'){
                jX=i+1;
                jY=j+1;
            }
            else
                graph[i+1][j+1]= 1;
        }
    }
    cautareBFS(rX,rY,jX,jY);
    int minDist = 100001, x, y;

    for(int i = 0; i < solutie.size(); i++){
        x = solutie[i].x;
        y = solutie[i].y;
        if(cautR[x][y]==cautJ[x][y])
            minDist = std::min(minDist,cautR[x][y]);
    }
    int miniPoz=1000000,miniIndex;
    for(int i = 0; i < solutie.size(); i++){
        x = solutie[i].x;
        y = solutie[i].y;
        if(cautR[x][y]==cautJ[x][y] && minDist == cautR[x][y]){
            miniPoz=std::min(miniPoz,x);
            miniIndex=i;
        }
    }
    x = solutie[miniIndex].x;
    y = solutie[miniIndex].y;
    out << minDist+1 << " " << x << " " << y;

    return 0;
}