Cod sursa(job #2365164)

Utilizator NashikAndrei Feodorov Nashik Data 4 martie 2019 12:17:40
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.1 kb
//#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

queue<pair<int,pair<int,int> > > pq;
int v[105][105],costr[105][105],costj[105][105];
int f[105][105];
int main()
{
    ifstream cin("rj.in");
    ofstream cout("rj.out");

    int n,m,iri,irj,iji,ijj;
    char ch;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin.get();
        for(int j=1;j<=m;j++){
            cin.get(ch);
            if(ch==' ')
                v[i][j]=0;
            if(ch=='X')
                v[i][j]=1;
            if(ch=='R'){
                iri=i;
                irj=j;
                v[i][j]=2;
            }
            if(ch=='J'){
                iji=i;
                ijj=j;
                v[i][j]=3;
            }
        }
    }
    ///vom utiliza lee incepand din R si din J
    pq.push(make_pair(iri,make_pair(irj,1)));
    while(pq.empty()==false){
        pair<int,pair<int,int> > a=pq.front();
        pq.pop();
        if(f[a.first][a.second.first]==1 or a.first==0 or a.second.first==0 or a.first==n+1 or a.second.first==m+1 or v[a.first][a.second.first]==1)
            continue;
        else{
            f[a.first][a.second.first]=1;
            costr[a.first][a.second.first]=a.second.second;
            int i=a.first,j=a.second.first,cost=a.second.second+1;
            pq.push(make_pair(i+1,make_pair(j,cost)));
            pq.push(make_pair(i-1,make_pair(j,cost)));
            pq.push(make_pair(i+1,make_pair(j+1,cost)));
            pq.push(make_pair(i+1,make_pair(j-1,cost)));
            pq.push(make_pair(i-1,make_pair(j+1,cost)));
            pq.push(make_pair(i-1,make_pair(j-1,cost)));
            pq.push(make_pair(i,make_pair(j+1,cost)));
            pq.push(make_pair(i,make_pair(j-1,cost)));
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            f[i][j]=0;
    }
    pq.push(make_pair(iji,make_pair(ijj,1)));
    while(pq.empty()==false){
        pair<int,pair<int,int> > a=pq.front();
        pq.pop();
        if(f[a.first][a.second.first]==1 or a.first==0 or a.second.first==0 or a.first==n+1 or a.second.first==m+1 or v[a.first][a.second.first]==1)
            continue;
        else{
            f[a.first][a.second.first]=1;
            costj[a.first][a.second.first]=a.second.second;
            int i=a.first,j=a.second.first,cost=a.second.second+1;
            pq.push(make_pair(i+1,make_pair(j,cost)));
            pq.push(make_pair(i-1,make_pair(j,cost)));
            pq.push(make_pair(i+1,make_pair(j+1,cost)));
            pq.push(make_pair(i+1,make_pair(j-1,cost)));
            pq.push(make_pair(i-1,make_pair(j+1,cost)));
            pq.push(make_pair(i-1,make_pair(j-1,cost)));
            pq.push(make_pair(i,make_pair(j+1,cost)));
            pq.push(make_pair(i,make_pair(j-1,cost)));
        }
    }
    int minim=1000000,c1,c2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            if(costr[i][j]==costj[i][j] and costr[i][j]!=0){
                if(minim>costr[i][j]){
                    minim=costr[i][j];
                    c1=i;
                    c2=j;
                }
            }
    }
    cout<<minim<<" "<<c1<<" "<<c2;
    return 0;
}