Cod sursa(job #2668283)

Utilizator tudosemihaitudose mihai tudosemihai Data 4 noiembrie 2020 18:48:32
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

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


int n, m;
int graph[110][110],rX,rY,jX,jY;
bool found;

std::vector<std::pair<int,int>> romeo,julieta;
int romeoDist[110][110],julietaDist[110][110];

int main() {
    in >> n >> m;
    char citire_in_cplusplus[110];
    in.getline(citire_in_cplusplus,m);
    for (int i = 0; i < n; i++) {
        char linie[100];
        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'){
                graph[i+1][j+1]= 1;
                romeoDist[i+1][j+1] = 1;
                rX=i+1;
                rY=j+1;
            }
            else if(linie[j]=='J'){
                graph[i+1][j+1]= 1;
                julietaDist[i+1][j+1] = 1;

                jX=i+1;
                jY=j+1;
            }
            else
                graph[i+1][j+1]= 2;
        }
    }
    for (int i = 0; i <= n ; i++)
        graph[i][0] = -2;
    for (int i = 0; i <= m ; i++ )
        graph[0][i] = -2;

    romeo.push_back(std::make_pair(rX,rY));
    for(int i = 0; i < romeo.size(); i++) {
        int x,y,x1,y1;
        x1=romeo[i].first;
        y1=romeo[i].second;
        int depX[8]={  0, 0, 1, 1, 1, -1,-1,-1};
        int depY[8]={ -1, 1,-1, 0, 1, -1, 0, 1};
        for(int j = 0; j < 8 ; j++) {
            x = x1+depX[j];
            y = y1+depY[j];
            if(graph[x][y]>0 && x <= n && y <= m)
                if(romeoDist[x][y]==0) {
                    romeoDist[x][y]=romeoDist[x1][y1] + 1;
                    romeo.push_back(std::make_pair(x,y));
                }
        }
    }

    julieta.push_back(std::make_pair(jX,jY));
    for(int i = 0; i < julieta.size(); i++) {
        int x,y,x1,y1;
        x1=julieta[i].first;
        y1=julieta[i].second;
        int depX[8]={  0, 0, 1, 1, 1, -1,-1,-1};
        int depY[8]={ -1, 1,-1, 0, 1, -1, 0, 1};
        for(int j = 0; j < 8 ; j++) {
            x = x1+depX[j];
            y = y1+depY[j];
            if(graph[x][y]>0 && x <= n && y <= m)
                if(julietaDist[x][y]==0) {
                    julietaDist[x][y]=julietaDist[x1][y1] + 1;
                    julieta.push_back(std::make_pair(x,y));
                }
        }
    }




    int minX = 100001,minY = 100001,minDist = 100001;

    for (int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(romeoDist[i][j] == julietaDist[i][j] && graph[i][j]>0 && romeoDist[i][j]>0 && romeoDist[i][j]<minDist){
                minDist=romeoDist[i][j];
                minX = i;
                minY = j;
            }

    out << minDist << " " << minX << " " << minY;

    return 0;
}