Cod sursa(job #2788350)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 25 octombrie 2021 16:13:02
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.07 kb
#include<bits/stdc++.h>
using namespace std;

const int inf=(1e9);

const int dim=(1e5);

char buff[dim+5];

int pos=0;

int cnt[7505];

void read(int &nr)
{
    int semn=1;
    nr=0;


    while(!isdigit(buff[pos]))
    {

        if(buff[pos]=='-') semn=-1;

        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }


    }


    while(isdigit(buff[pos]))
    {
        nr=nr*10+buff[pos]-'0';
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }

    nr*=semn;

}

class Graph
{

private:

    int m_nodes;

    vector< vector< pair<int,int> > > m_adjList;

    vector<pair<int, pair<int,int> > > m_edges;

    vector<bool> m_visited;

    bool m_areLabeled;

public:

    Graph(int nodes,bool areLabeled)
    {
        m_nodes=nodes;
        m_areLabeled=areLabeled;

        m_adjList.resize(nodes+5);

    }


    void addEdge(int from, int to, int cost)
    {
        m_adjList[from].push_back(make_pair(to,cost));
        m_edges.push_back(make_pair(from,make_pair(to,cost)));
    }

    void resetVisited()
    {
        m_visited.resize(m_nodes+5);

        for(int i=0;i<=m_nodes;i++)
            m_visited[i]=0;
    }


    vector<int> bfs(int source)
    {
        deque<int> q;

        vector<int> distances(m_nodes+5,-1);

        distances[source]=0;

        q.push_back(source);


        while(!q.empty())
        {
            int current = q.front();

            q.pop_front();

            for(auto it: m_adjList[current])
            {
                if(distances[it.first]==-1)
                {
                    distances[it.first]=1+distances[current];
                    q.push_back(it.first);
                }
            }

        }


        return distances;

    }

    void dfs(int node)
    {
        m_visited[node]=1;

        for(auto it:m_adjList[node])
        {
            if(m_visited[it.first]) continue;
            dfs(it.first);
        }
    }

    int getCC()
    {

        resetVisited();

        int ans=0;
        for(int i=1;i<=m_nodes;i++)
            if(!m_visited[i]) dfs(i),ans++;


        return ans;
    }



};

unordered_map<int,int> M;

inline int getIndex(int n,int m,int i,int j)
{
    return i*m+j;
}
char a[105][105];
pair<int,int> romeo,juliet;
int d[10][3]= {{0,0,1},{0,0,-1},{0,-1,0},{0,1,0},{0,-1,-1},{0,-1,1},{0,1,-1},{0,1,1}};
int main()
{

    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    int n,m,x,y,source;

    scanf("%d%d",&n,&m);


    Graph G(n*m,0);

    for(int i=0;i<n;i++)
    {
        scanf("\n");
        //scanf("%s",a[i]);

        for(int j=0;j<m;j++)
        {
            scanf("%c",&a[i][j]);

            if(a[i][j]=='R') romeo=make_pair(i,j);
                else
            if(a[i][j]=='J') juliet=make_pair(i,j);



        }
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int currentPosition=getIndex(n,m,i,j);

            for(int k=1;k<=8;k++)
            {
                int ii = i + d[k][1];
                int jj = j + d[k][2];

                if(ii<0 || jj<0 || ii>=n || jj>=m) continue;

                if(a[ii][jj]=='X') continue;

                G.addEdge(getIndex(n,m,i,j),getIndex(n,m,ii,jj),0);
            }
        }
    }


    vector<int> d1 = G.bfs(getIndex(n,m,romeo.first,romeo.second));
    vector<int> d2 = G.bfs(getIndex(n,m,juliet.first,juliet.second));

    int minim=INT_MAX;


    pair<int,int> best;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(d1[getIndex(n,m,i,j)]!=-1 && d1[getIndex(n,m,i,j)]==d2[getIndex(n,m,i,j)] && d1[getIndex(n,m,i,j)]<minim)
            {
                minim=d1[getIndex(n,m,i,j)];
                best=make_pair(i,j);
            }
        }
    }

    printf("%d %d %d\n",minim+1,best.first+1,best.second+1);




    return 0;
}