Cod sursa(job #2570344)

Utilizator evelina.nitoiuNitoiu Evelina evelina.nitoiu Data 4 martie 2020 16:17:05
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");

int di[]={1, 1, 1, 0, 0, -1, -1, -1};
int dj[]={1, 0, -1, 1, -1, 1, 0, -1};

int ij,jj,jr,ir;
int julieta[105][105],romeo[105][105],v[105][105];
int n,m;
int sol,isol,jsol;
void lee1(){
    queue<pair<int,int>>q;
    q.push(make_pair(ij,jj));
    julieta[ij][jj]=1;
    while(!q.empty()){
        int i=q.front().first;
        int j=q.front().second;
        q.pop();
        for(int k=0;k<8;k++){
            int iv=i+di[k];
            int jv=j+dj[k];
            if(iv>=1&&iv<=n&&jv>=1&&jv<=m&&v[iv][jv]==0&&julieta[iv][jv]==0)
            {
                q.push(make_pair(iv,jv));
                julieta[iv][jv]=1+julieta[i][j];
            }
//            if(iv==ir&&jv==jr)
//                out<<julieta[iv][jv]/2;
        }
    }
}
void lee2(){
    queue<pair<int,int>>q;
    q.push(make_pair(ir,jr));
    romeo[ir][jr]=1;
    while(!q.empty()){
        int i=q.front().first;
        int j=q.front().second;
        q.pop();
        for(int k=0;k<8;k++){
            int iv=i+di[k];
            int jv=j+dj[k];
            if(iv>=1&&iv<=n&&jv>=1&&jv<=m&&v[iv][jv]==0&&romeo[iv][jv]==0)
            {
                q.push(make_pair(iv,jv));
                romeo[iv][jv]=1+romeo[i][j];
            }
//            if(iv==ij&&jv==jj)
//                return;
        }
    }
}
int main()
{
//    char s[100];
//    cin>>s+1;
//    cout<<s;
    sol=INT_MAX;
    in>>n>>m;in.get();
    for(int i=1;i<=n;i++){
        char t[105];
        in.getline(t,105);
        //cout<<t<<"\n";
        for(int j=1;j<=m;j++)
            if(t[j-1]=='X')
                v[i][j]=1;
            else
                if(t[j-1]=='R')
                {
                    ir=i;
                    jr=j;
                    //v[i][j]=2;
                }
                else
                    if(t[j-1]=='J')
                    {
                        ij=i;
                        jj=j;
                        //v[i][j]=3;
                    }
    }
    //bordare();
//    cout<<"\n";
//     for(int i=1;i<=n;i++){
//        for(int j=1;j<=m;j++)
//            cout<<v[i][j]<<" ";
//        cout<<"\n";
//    }
    lee1();
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=m;j++)
//            cout<<julieta[i][j]<<" ";
//        cout<<"\n";
//    }
    lee2();
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=m;j++)
//            cout<<romeo[i][j]<<" ";
//        cout<<"\n";
//    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(v[i][j]!=1&&romeo[i][j]>0&&julieta[i][j]>0&&romeo[i][j]==julieta[i][j])
                if(romeo[i][j]<sol||(romeo[i][j]==sol&&i<isol)||(romeo[i][j]==sol&&i==isol&&j<jsol)){
                    sol=romeo[i][j];
                    isol=i;
                    jsol=j;
                }
    out<<sol<<" "<<isol<<" "<<jsol;
    return 0;
}