Cod sursa(job #2668233)

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

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


int n, m, start;
int dist[100005],bfs[100005],graph[110][110],rX,rY,jX,jY;
bool found;

std::vector<int> g[100005],next;
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'){
                rX=i+1;
                rY=j+1;
            }
            else if(linie[j]=='J'){
                jX=i+1;
                jY=j+1;
            }
            else
                graph[i+1][j+1]= 1;
        }
    }
    for (int i = 0; i <= n ; i++)
        graph[i][0] = graph[0][i] = -2;
    for (int i = 0; i < 100005; i++)
        dist[i]=-1, bfs[i]=-1;

    romeo.push_back(std::make_pair(rX,rY));
    dist[start] = 0;
    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)
                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));
    dist[start] = 0;
    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)
                if(julietaDist[x][y]==0) {
                    julietaDist[x][y]=julietaDist[x1][y1] + 1;
                    julieta.push_back(std::make_pair(x,y));
                }
        }
    }


    for( int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            std:: cout << romeoDist[i][j] << " ";
        std:: cout << '\n';
    }

    std:: cout << '\n';

    for( int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            std:: cout << julietaDist[i][j] << " ";
        std:: cout << '\n';
    }

    std:: cout << '\n';


    for( int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(romeoDist[i][j]==julietaDist[i][j] && romeoDist[i][j]>0) {
                out << romeoDist[i][j] + 1 << " " << i << " " << j;
                goto exit;
            }
        }
    }
    exit:
    return 0;
}