Cod sursa(job #3205314)

Utilizator Bogdan345Marius Mihalache Bogdan345 Data 19 februarie 2024 11:42:32
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
queue<pair<int,int>>q;
vector<vector<char>>mat;
vector<vector<int>>distantaR,distantaJ;
vector<int>x={1,-1,0,0,1,1,-1,-1},y={0,0,1,-1,-1,1,-1,1};
const int inf=1e9;
void algLee(int n,int m,pair<int,int>R,pair<int,int>J){
    q.push({R.first,R.second});
    while(!q.empty()){
        pair<int,int>poz=q.front();
        q.pop();
        int i,j;
        for(int u=0;u<=7;u++){
            i=poz.first+x[u];
            j=poz.second+y[u];
            if(i>n || i<1 || j>m || j<1 || mat[i][j]=='X'){
                continue;
            }
            if(distantaR[i][j]>distantaR[poz.first][poz.second]+1){
                distantaR[i][j]=distantaR[poz.first][poz.second]+1;
                q.push({i,j});

            }
        }
    }
      q.push({J.first,J.second});
      while(!q.empty()){
        pair<int,int>poz=q.front();
        q.pop();
        int i,j;
        for(int u=0;u<=7;u++){
            i=poz.first+x[u];
            j=poz.second+y[u];
            if(i>n || i<1 || j>m || j<1 || mat[i][j]=='X'){
                continue;
            }
            if(distantaJ[i][j]>distantaJ[poz.first][poz.second]+1){
                distantaJ[i][j]=distantaJ[poz.first][poz.second]+1;
                q.push({i,j});

            }
        }
    }
    int rasp=inf;
    int a,b;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(distantaJ[i][j]==distantaR[i][j] && rasp>distantaR[i][j]){
                rasp=distantaR[i][j];
                a=i;
                b=j;
            }
        }
    }
    cout<<rasp<<" "<<a<<" "<<b;
}
int main(){
    int n,m;
    cin>>n>>m;
    mat.resize(n+1,vector<char>(m+1));
    distantaJ.resize(n+1,vector<int>(m+1,inf));
    distantaR.resize(n+1,vector<int>(m+1,inf));
    string s;
    for(int i=0;i<=n;i++){
        getline(cin,s);
        for(int j=0;j<s.size();j++){
            mat[i][j+1]=s[j];
        }
    }
    pair<int,int>R,J;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mat[i][j]=='R'){
                distantaR[i][j]=1;
                R.first=i;
                R.second=j;
            }else if(mat[i][j]=='J'){
                 distantaJ[i][j]=1;
                 J.first=i;
                 J.second=j;
            }
        }
    }
    algLee(n,m,R,J);
}