Cod sursa(job #2929227)

Utilizator Bogdan345Marius Mihalache Bogdan345 Data 25 octombrie 2022 12:08:18
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <vector>
#include <queue>
#include<fstream>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
vector<int>dirX={1,1,1,0,0,-1,-1,-1};
vector<int>dirY={-1,1,0,-1,1,0,1,-1};
vector<vector<bool>>obstacol;
queue<pair<int,int>>q;
const int inf=1e9;
int distanta[2][101][101];
  int n,m;
void algLee(int tip,pair<int,int>coordonate){
    q.push(coordonate);
    distanta[tip][coordonate.first][coordonate.second]=1;
    while(!q.empty()){
        pair<int,int>pozCurenta=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int x=pozCurenta.first+dirX[i];
            int y=pozCurenta.second+dirY[i];
            if(x<1 || x>n || y<1 || y>m){
                continue;
            }
            if(distanta[tip][x][y]!=inf){
                continue;
            }
            if(obstacol[x][y]==true){
                continue;
            }
          distanta[tip][x][y]=distanta[tip][pozCurenta.first][pozCurenta.second]+1;
          q.push({x,y});
        }
    }
}
int main(){
    fin>>n>>m;
    string s;
    getline(fin,s);
    obstacol.resize(n+1,vector<bool>(m+1,false));
    pair<int,int>R,J;
    for(int i=1;i<=n;i++){
        getline(fin,s);
        for(int j=0;j<m;j++){
            if(s[j]=='J'){
                J={i,j+1};
            }
             if(s[j]=='R'){
                R={i,j+1};
            }
            if(s[j]=='X'){
                obstacol[i][j+1]=true;
            }
             distanta[1][i][j+1]=inf;
             distanta[0][i][j+1]=inf;
        }
    }
    algLee(1,R);
    algLee(0,J);
    int MIN=inf;
    pair<int,int>raspuns;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(distanta[1][i][j]==distanta[0][i][j] && distanta[1][i][j]<MIN){
                MIN=distanta[1][i][j];
                raspuns={i,j};
            }
        }
    }
    fout<<MIN<<" "<<raspuns.first<<" "<<raspuns.second;
}